PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 315 / デジタルルート時計(1)

Sam と Max は2個のデジタル時計を「デジタルルート(数字根)時計」に作り変えるよう依頼されている。
デジタルルート時計は数字根をステップごとに計算するデジタル時計である。

f:id:variee:20170927013825g:plain

時計に数字が与えられると,時計は数字を表示し,計算を開始する。たとえば,時計に 137 という数が与えられると"137"→"11"→"2" と表示してから真っ黒になり,次の数を待つ。

各デジタル数字はセグメント状のライトから構成される。横セグメントが3本(上,中,下)と縦セグメントが4本(左上,右上,左下,右下)である。数 "1" は右上と右下の縦セグメントでできており,数 "4" は中の横セグメントと左上, 右上, 右下の縦セグメントからできている。数 "8" はすべてのセグメントが点灯する。

時計はセグメントを点灯/消灯させるときに限りエネルギーを消費する。"2" を点灯させるには 5 回の遷移を要する。"7" は 4 回だけ遷移を要する。

Sam と Max は2個の異なる時計を作る。

Sam の時計は 137 のような数を与えられると "137" を表示し,パネルを消灯してから次の数("11")を点灯し,再び消灯してそして最終的に最後の数("2")を点灯,しばらくして消灯する。たとえば 137 では Sam の時計は次のように動く。

  • "137":(2 + 5 + 4) x 2 = 22 回の遷移("137" の点灯/消灯)
  • "11" :(2 + 2) x 2 = 8 回の遷移("11" の点灯/消灯)
  • "2" :(5) x 2 = 10 回の遷移("2" の点灯/消灯)

合計で 40 回の遷移である。

Max の時計は異なる動きをする。パネル全体を消灯するのではなく,次の数に必要のないセグメントのみを消灯するという賢いやり方である。数 137 に対して Max の時計は次のように動く。

"137":2 + 5 + 4 = 11 回の遷移("137" の点灯)
     7 回の遷移(数 "11" に必要ないセグメントの消灯)
"11" :0 回の遷移(数 "11" はすでに正しく点灯済み)
     3 回の遷移(始めの "1" と2つ目の "1" の下部分を消灯;
     上部分は数 "2" と共通である)
"2" :4 回の遷移("2" にするため残りのセグメントを点灯)
     5 回の遷移("2" を消灯)

合計で 30 回の遷移である。

もちろん,Max の時計のほうが Sam より電力の消費が少ない。2つの時計に A = 10^7 から B = 2 x 10^7 の間の素数が与えられる。Sam の時計で必要な遷移の総数と Max の時計で必要な遷移の総数の差を求めよ。

Problem 315 - Project Euler


今回は Sam について考えます。

数字根とは正の整数の各位の和を求める操作を繰り返して最終的に得られる1桁の数のことです。Mathematica の場合,Total@IntegerDigits[n] の NestWhile で計算できます。

パネルを表示するコストは 1→2, 2→5 のような写像で求めます。計算には約10秒かかります。


コストを求める前に Tally で各数字が何回使われるかを数えると若干早くなります。こちらは6.6秒。


Max のコストも同じようにして求められますが,2人のコストを求めた上で差を求めるのは無駄が多いです。次回,最終的な答えを求める記事では Sam と Max の差だけ計算します。