PEをMathematicaで

Project Eulerに挑戦してみよう

算チャレ1036回を解いてみた

「算数にチャレンジ!!」さんの第1036回の問題を解いてみました。

2つの整数アとイがあります。アとイはともに1以上100以下の整数です。ア+イが偶数で,ア×2+イ×3 が5の倍数となるような(ア, イ)は何組あるでしょうか。
http://www.sansu.org/used-html/index1036.html

www.sansu.org

Mathematicaで解く

まずはそのまま解いてみました。答えは1000組。

妙にきれいな答えが出て不思議に思ったので,一般解も求めてみました。
連立合同式を Reduce すると
 x\equiv y\pmod{10}
が答えだとわかります。

1 ≦ x ≦10, 1 ≦ y ≦10 での解は

 x=y=k\quad (1\leqq k\leqq 10)

の10個。x, y それぞれに「+10」が10回ずつできるので,求める個数は

 10\cdot 10^2=1000\,\text{個}

となります。

手計算で解くなら

手計算で解く場合, 2x+3y\equiv 0\pmod{5} の 3 を -2 に変えることがポイントだと思います。

 2(x-y)\equiv 0\pmod{5}\quad \therefore x-y\equiv 0\pmod{5}

これだけで 1 ≦ x ≦10, 1 ≦ y ≦10 の解の候補が (1, 1), (1, 6) などの 2*10=20 個に減ります。「和が偶数」の条件でさらに半分の10個にしぼれて,これが 1 ≦ x ≦10, 1 ≦ y ≦10 の解です。あとは「+10」が10回ずつできることを使えば解けます。

Project Euler 239 / 擬似フォーチュン数

偶数の正整数 N は 2 の累乗であるか素因数がすべて連続した素数である場合,許容的と呼ぶ。最初の 12 個の許容的な数は 2,4,6,8,12,16,18,24,30,32,36,48 である。

N が許容的であるとき,N+M が素数である最小の整数 M > 1 を N の擬似フォーチュン数(pseudo-Fortunate number)と呼ぶ。

たとえば N=630 は許容的である。630 は偶数で,その素因数は連続する素数 2, 3, 5, 7 である。

631 より大きい次の素数は 641 であり,630 の擬似フォーチュン数は M=11 である。同様に 16 の擬似フォーチュン数は 3 である。

10^9 未満の許容的な数 N に対して, すべての異なる擬似フォーチュン数の合計を求めよ。

Problem 293 - Project Euler


問題文の流れは

  1. 許容的な数を求める
  2. 擬似フォーチュン数を求める

ですが,擬似フォーチュン数の方が簡単なのでこちらから書きました。
NextPrime を使います。

次に許容的な数を求めます。「10^9 未満」の条件から,使える素数は9個です。

「2だけ使った数の集合を作る」→「その各要素に3をかけたものの集合を作る」のような操作を繰り返して,最後に和集合をとります。
NestWhileList と AppendTo で書きました。

計算時間は約0.3秒で,許容的な数は6656個,相異なる擬似フォーチュン数は41個でした。ダブりまくりです。

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

前回の記事の続きです。Sam と Max の表示コストをそれぞれ計算して差をとるかわりに,両者の差だけ計算します。

variee.hatenadiary.com

桁ごとのコスト差

表示がないことをΦであらわします。ある桁の表示が a から b に変わるとき,Sam は「a→Φ→b」,Max は「a→b」と推移するので表示コストの差は次の形の式で求められます。

 g(a,\, b)=f(a,\, \phi)+f(\phi,\, b)-f(a,\, b)

全体としての差

この問題では 10^7 以上 2*10^7 以下の数が相手なので,時計の表示は次のように変化します。最高でも3回しか推移しません。

  1. 8桁の数
  2. 1+9*7=64以下の数(2桁以下)
  3. 7+9=16以下の数(2桁以下)
  4. 1桁の数

最初に8桁の数を表示するところでは差は生じません。また,8桁→2桁のとき Sam も Max も上位6桁は「a→Φ」型の変化をするので,ここでも差は生じません。
元の数を n,各位の数字の和を f(n) であらわすと

 n→f(n)→f^2(n)→f^3(n)

のかわりに

 \bmod(n,100)→f(n)→f^2(n)→f^3(n)

を考えればいいことになります。

実装

問題文には 10^7 という大きな数が書いてありますが,実際に相手にするのは2桁以下の数から2桁以下の数へ変化するときのコスト差です。

「1桁→2桁」(最初だけおこりうる),「2桁→2桁」,「2桁→1桁」の各場合に対応できる関数を書いてできあがりです。約10秒でした。

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 の差だけ計算します。

Project Euler 234 / 半分割可能数

整数n(≥4)に対して最大の素数(≤√n)を n の下位素数平方根(lower prime square root)とし,lps(n)であらわす。同様に最小の素数(≥√n)を n の上位素数平方根(upper prime square root)とし,ups(n)であらわす。

lps(4) = 2 = ups(4), lps(1000) = 31, ups(1000) = 37 である。

lps(n) と ups(n) のどちらかが n を割り切るが,両方ではないとき整数n(≥4)を半分割可能(semidivisible)と呼ぶ。

15 を超えない半分割可能な数は8, 10, 12で,それらの合計は 30 である。15 は lps(15) = 3 と ups(15) = 5の両方の倍数なので半分割可能でない。さらに例を挙げると,1000 までの半分割可能な整数 92 個の合計は 34825 である。

999966663333 を超えない半分割可能な数全ての合計を求めよ。

Problem 234 - Project Euler


lps(n)=ups(n) だと「両方ではない」の条件をみたさないので,n は平方数ではありません。 p< \sqrt{n}< q をみたす連続する素数 p, q が存在します。平方すると

 p^2< n< q^2

この範囲で
(p の倍数の和) + (q の倍数の和) - (pq の倍数の和)*2
を計算して足しあわせます。

ただし,最後の素数 p についてだけ,n が 999966663333 を超えるかどうかのチェックが必要です。下のコード中で sum1=0 なのですが,一応調べました。


Sum を2次関数であらわに書くと若干早くなります。1秒→0.8秒の微妙な変化ですが。