PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 303 / 小さい桁を持つ倍数

正の整数 n の倍数の中で各位の数字がすべて2以下(10進法)のものの最小値を f(n) とする。
f(2)=2, f(3)=12, f(7)=21, f(42)=210, f(89)=1121222

Σ[n=1...100] f(n)/n =1136107 である。

Σ[n=1...10000] f(n)/n を求めよ。

Problem 303 - Project Euler

f(n) を求める

f(n) を求める方法をいろいろ試してみました。

f1(n) は10進法で考えています。f[99]一つに10秒かかっています。i を1ずつ増やしていく操作は10回中7回が無駄で,この方法はダメですね。

f2(n) は3進法その1です。BaseForm で3進法の数を作ると,120(3)の「(3)」のような無駄な項がついてしまい,これを削除する方法がわからなかったので 0, 1, 2 を15個並べたリストを作って,数に直しています。あまり高速化できなかったと,15桁では足りないので,この方法も却下。

f3(n) は3進法その2です。邪魔な「(3)」をとる方法がわかりました。

  • IntegerDigits[n, 3] で3進法表示の各位の数字を求める
  • FormDigits で数に直す

この方法はさすがに速くて,f1(n)の280倍です。

f(999), f(9999)の処理

Σ計算する上での難敵は f(999), f(9999) です。これらは非常に大きな値をとり,f3(n)を使ってもかなり時間がかかります。

  • f(999)=111222222222222
  • f(9999)=11112222222222222222

しかし,実はこれらの値は暗算で求めることができます。

1000 ≡ 1 (mod 999) から,ある数が999で割り切れる条件は3桁ごとに区切ったものの和が999で割り切れることです。0, 1, 2 しか使わずにこの条件をみたすため,
111+222*4=999
を利用して
111,222,222,222,222
と並べます。この数が最小値 f(999) です。

f(9999) も同様。10000 ≡ 1 (mod 9999) なので4桁ごとに区切って足します。
1111+2222*4=9999 から
f(9999)=1111,2222,2222,2222,2222

999 の倍数の f(n) も簡単に求められます。

  • 2の倍数 → 一の位が偶数
  • 4の倍数 → 下2桁が4の倍数
  • 5の倍数 → 一の位が0か5
  • 8の倍数 → 下3桁が8の倍数
  • 10の倍数 → 一の位が0

これらと999の倍数条件を組みあわせることで
f(999*k) (k=2, 4, 5, 8, 10)
が求められます。以上を利用すると1分の壁を破れます。

f(999*3) なども求めておくと更に時間を短縮できますが,さすがにここまでするのはちょっとやりすぎな気がします。