PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 38 / パンデジタル倍数

192に1, 2, 3を掛けてみよう。

  • 192×1 = 192
  • 192×2 = 384
  • 192×3 = 576

積を連結することで1から9のパンデジタル数192384576が得られる。192384576を192と(1,2,3)の連結積と呼ぶ。

同じようにして, 9を1,2,3,4,5と掛けて連結することでパンデジタル数918273645が得られる。これは9と(1,2,3,4,5)との連結積である。

整数と(1,2,...,n) (n>1)との連結積として得られる9桁のパンデジタル数の中で最大のものはいくつか?

Problem 38 - Project Euler


候補のしぼりこみが有効な問題でした。

(a桁の数x)*(1,2,...,n)=(9桁のパンデジタル数)

とおきます。最大値を求めたいのでxの首位の数字は9。xは2倍,3倍,……でa+1桁になります。上式両辺の桁数に注目しましょう。

a+(a+1)(n-1)=9

Mathematica によると解は (a, n)=(1, 5),(4,2) の2つです。(1, 5)の結果は問題文中に与えられているので, (4, 2) について調べれば十分です。


9ではじまる4桁の数xに対して,xと2xを連結した数はx*10^5+2x。これがパンデジタルかどうか調べました。


候補となる数は3つしかないんですね。

Project Euler 23 / 非過剰数和

完全数とはその数の真の約数の和がそれ自身と一致する数のことである。たとえば28の真の約数の和は1+2+4+7+14=28であるので,28は完全数である。

真の約数の和がその数よりも少ないものを不足数といい,真の約数の和がその数よりも大きいものを過剰数と呼ぶ。

12は1+2+3+4+6=16となるので最小の過剰数である。よって2つの過剰数の和で書ける最少の数は24である。数学的な解析により,28123より大きい任意の整数は2つの過剰数の和で書けることが知られている。2つの過剰数の和で表せない最大の数がこの上限よりも小さいことは分かっているのだが,この上限を減らすことができていない。

2つの過剰数の和で書き表せない正の整数の総和を求めよ。

Problem 23 - Project Euler


2つの過剰数の和で表せる数の集合を作って,その総和を1~28123の総和から引けばいいはず。地道な方法で解いてしまった……

  • 過剰数のリストを作る(myList1)
  • 過剰数の和のリストを作る(myList2)
  • 総和の引き算


追記

mathworld によると,20161より大きい数は過剰数の和であらわされるそうです。これをもとに検索範囲をせばめると,計算時間が半分になります。

Abundant Number -- from Wolfram MathWorld

Project Euler 32 / パンデジタル積

すべての桁に1からnまでの数字が一度だけ使われているn桁の数をパンデジタル(pandigital)であるということにしよう。たとえば5桁の数 15234 は1から5のパンデジタルである。

7254 は面白い性質を持っている。39×186=7254 と書け,掛けられる数,掛ける数,積が1から9のパンデジタルとなる。

掛けられる数/掛ける数/積が1から9のパンデジタルとなるような積の総和を求めよ。

HINT:いくつかの積は1通り以上の掛けられる数/掛ける数/積の組み合わせを持つが,1回だけ数え上げよ。

Problem 32 - Project Euler


1から9までの数の順列を適当に区切って,条件をみたすかどうか調べることも考えたのですが,時間がかかりそうなので止めました。

n とその約数 k について n, k, n/k がパンデジタルかどうか調べます。具体的には IntegerDigits[ ] で各数の桁数字を拾って,その Union が {1,2,...,9} と一致するかどうか調べました。

計算量を減らすため,積の候補のしぼりこみをおこなっています。

(a桁の数x)*(b桁の数y)=(c桁の数z)とおきます。

10^(a-1)≦x<10^a, 10^(b-1)≦y<10^b から

10^(a+b-2)≦xy=z<10^(a+b)

一方,10^(c-1)≦z<10^c で,これらを同時にみたす c が存在するには

a+b-2< c, c-1< a+b

が必要です。a+b+c=9 を使って a,b を消去すると 7/2< c<5。cは整数なので c=4 です。各桁の数字がすべて異なることも考えると 1234 以上 9876 以下の数について調べればよいとわかります。

ちなみに,条件をみたす数は7個でした。

Project Euler 43 / 部分文字列被整除性

数1406357289は0から9のパンデジタル数である(0から9が一度ずつあらわれる数)。この数は部分文字列が面白い性質を持っている。

d1を上位1桁目,d2を上位2桁目の数とし,以下順にdnを定義する。この記法を用いると次のことが分かる。

  • d2d3d4=406 は 2 で割り切れる
  • d3d4d5=063 は 3 で割り切れる
  • d4d5d6=635 は 5 で割り切れる
  • d5d6d7=357 は 7 で割り切れる
  • d6d7d8=572 は 11 で割り切れる
  • d7d8d9=728 は 13 で割り切れる
  • d8d9d10=289 は 17 で割り切れる

このような性質をもつ0から9のパンデジタル数の総和を求めよ。

Problem 43 - Project Euler


パンデジタル数は Permutations[Range[0, 9]] で作ります。これで {0,1,...,9} を並べ替えたすべてのリストができます。

その後の処理はこうです。

  1. Take[x, {i + 1, i + 3}]でリスト x の i+1 桁目から i+3 桁目までを取り出す
  2. FromDigits で数に直す
  3. i 番目の素数 Prime[i] で割り切れるかどうかを Divisible で調べる
  4. チェックを通ったリストを FromDigits で数に直して,その和を求める


ちなみに条件をみたす数は6個でした。これは首位の数字が0の数を含めても変わりません。

Project Euler 46 / もうひとつのゴールドバッハ予想

Christian Goldbachはすべての奇合成数は平方数の2倍と素数の和で表せると予想した。

  • 9 = 7 + 2×1^2
  • 15 = 7 + 2×2^2
  • 21 = 3 + 2×3^2
  • 25 = 7 + 2×3^2
  • 27 = 19 + 2×2^2
  • 33 = 31 + 2×1^2

後にこの予想は誤りであることが分かった。平方数の2倍と素数の和で表せない最小の奇合成数はいくつか?

Problem 46 - Project Euler


2通りの方法で解きました。最初にやったのがこちら。奇合成数の集合 myList1 と「平方数の2倍と素数の和」の集合 myList2 を比較するというものです。

答えの5777を得るために10^4まで調べていますが,myList2の作り方がかなり適当です。n=5 を指定すると物理メモリの「変更済み」が多発して固まってしまいます。

そこで考え直したのがこちら。

この問題では最小値を求めるだけなので,前もって大きなリストを作っておく必要はありません。(n-素数)/2 が平方数になるかどうか調べていって SelectFirst しています。