PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 182 / RSA暗号

RSA暗号は以下のアルゴリズムにもとづいている。

  • 鍵生成
    • 二つの異なる素数 p と q を生成する
    • n=pq とし,φ=(p-1)(q-1) (=φ(n)) とする
    • 1< e< φ の範囲で gcd(e, φ)=1 となる整数eを決定する
  • 暗号化
    • 平文を [0, n-1] 中の整数 m とする。平文は以下の方法で [0, n-1] 中の整数に暗号化される
    • c=m^e mod n とし, c を暗号文とする
  • 復号
    • 暗号文を c とし以下の操作を行う
    • ed=1 mod φ となる d を計算する。m=c^d mod n が元の平文となる

ある e と m について m^e mod n=m となることがある。以下,m^e mod n=m となる m を公然の平文と呼ぶ。

公開鍵の一部 e を選ぶときには, 公然の平文が多くならないことが重要である。たとえば p = 19, q = 37 とする。このとき n = 19 x 37 = 703 であり,φ = 18 x 36 = 648 である。e = 181 とすると gcd(181, 648) = 1 であるが,すべての平文 m (0≤m≤n-1) が公然の平文となってしまう。e をどのように選んでも,必ずいくつかは公然の平文が存在する。

p = 1009, q = 3643 とする。このとき,公然の平文の個数が最小となるすべての e の総和を求めよ。
1< e< φ(1009, 3643) かつ gcd(e, φ)=1 とする。

本家:Problem 182 - Project Euler
日本語訳:Problem 187 - PukiWiki


公然の平文の個数は次の式で与えられます。証明は結構長いので省略しますが,「rsa unconcealed」などでググるとみつかります。

 \left\{1+gcd(e-1,\, p-1)\right\}  \left\{1+gcd(e-1,\, q-1)\right\}

各数の奇偶を考えると,この個数が最小になるのは次のような e を選んだときです。

 gcd(e-1,\, p-1)=gcd(e-1,\, q-1)=2

Project Euler 349 / ラングトンの蟻

黒白いずれかで色づけされた正方形の規則的な格子上をアリが動く。
アリは上下左右のいずれかを向いており,次のルールにしたがって隣接する正方形へ移動する。

  • 黒い正方形上にいる場合,その正方形の色を白に変えて反時計回りに向きを変え,1マス前進する
  • 白い正方形上にいる場合,その正方形の色を黒に変えて時計回りに向きを変え,1マス前進する

格子全体が白の状態から始めるとき,アリが 10^18 回動いた後の黒い正方形の数は何個あるか。

本家:Problem 349 - Project Euler
日本語訳:Problem 349 - PukiWiki

wikipediaで調べる

「ラングトンの蟻」は wikipedia に載っています。英語版のページに周期についての記述がありました。約一万ステップ後,周期104の動きを見せるようになるそうです。

  • After a few hundred moves, a big, irregular pattern of black and white squares appears. The ant traces a pseudo-random path until around 10,000 steps.
  • Finally the ant starts building a recurrent "highway" pattern of 104 steps that repeats indefinitely.

Langton's ant - Wikipedia

シミュレーション

mathematica による実装が Rosetta Code にありました。

Langton's ant - Rosetta Code

これをちょっといじって,104*100 ステップ後と104*105 ステップ後を見てみました。

これが104*100 ステップ後。
f:id:variee:20180614163952p:plain

次は104*105 ステップ後。
f:id:variee:20180614163947p:plain

左上に向かって伸びていく様子が見てとれます。次のようにして黒の数を調べてみたら,104ステップ毎に12ずつ増えていました。


計算

10^18 を104で割ると,商は 9615384615384615 で余りは 40 です。

40+104*100 ステップ後の黒の数は 772 なので,初項772,公差12の等差数列として計算して終了です。

Project Euler 516 / 5-スムーズトーシェント

5-スムーズ数とは最大の素因数が5を超えないような数のことである。ハミング数とも呼ばれる。

オイラーのトーシェント関数 φ(n) がハミング数となるような,L を超えない数 n の値の和を S(L) とする。
S(100)=3728

S(10^12) を求めよ。回答は 2^32 を法として答えよ。

本家:Problem 516 - Project Euler
日本語訳:Problem 516 - PukiWiki

どんな素数が使えるか

まずはトーシェント関数(ファイ関数)の復習から。p, q を異なる素数とします。

 \varphi(p^m q^n)=\varphi(p^m)\varphi(q^n)=p^{m-1} (p-1) q^{n-1} (q-1)

異なる素数について分割できること,2乗以上のとき p-1 が出てくることに注目すると,n を作るのに使える素数とその条件は次のとおりです。

  • 2, 3, 5は何回でも使える
  • p-1 がハミング数でない素数 p は使えない
  • p-1 がハミング数の素数 p (≠ 2, 3, 5) は1回まで使える

2, 3, 5だけであらわせる数は3429個あり(myList1), p-1 がハミング数になる 2, 3, 5 以外の素数は543個ありました(myList2)。

myList1 の数に myList2 の素数をいくつかかけて得られる 10^12 以下の数の総和が答えです。

累積和とバイナリサーチ

「myList1 の数を1つ取り出す」→「かけてよい数の総和を求める」→「積をとってその和を求める」でやりました。

そのまま書くとかなり時間がかかるので,「かけてよい数」の検索にバイナリサーチを使い,その和の計算には累積和を使っています。

1年前に考えたときはこれらを知らなかったので手も足も出なかったのですが,競プロを少しかじったおかげで解けました。

Project Euler 613 / Pythagorean Ant

30*40*50の直角三角形内にアリがいる。このアリがランダムに方向を選んで直進するとき,斜辺に達する確率を求めて小数第10位まで答えよ。

本家:Problem 613 - Project Euler

3辺の長さを3, 4, 5として考えます。三角形の頂点が
O(0, 0), A(3, 0), B(0, 4) となる座標系をとって,アリの座標を P(x, y) とします。

アリが斜辺に向かう確率は  \dfrac{\angle APB}{2\pi} です。これは x, y であらわせます。

 f(x, y)=\left(\dfrac{\pi}{2}+\arctan\dfrac{y}{3-x}+\arctan\dfrac{x}{4-y}\right)\div 2\pi

これの平均が答えです*1。重積分して,三角形の面積6で割りました。

数値積分すると 0.8 秒。

実は厳密解を求めることもできて 2.1 秒。

*1:最近の問題なので答えの数値は省略します

Project Euler 215 / 亀裂のない壁

2x1 と 3x1 のレンガを使って壁を作る。 ただし,水平方向に隣接したレンガ間の隙間が上下の層にまたがってはならない。つまり,伝播亀裂(running crack)がないようにする。

たとえば下図の 9x3 の壁は条件をみたしていない。赤線が伝播亀裂だからである。

f:id:variee:20180610143040g:plain

9x3 の亀裂のない壁は8通りある。これを W(9, 3)=8 と表す。
W(32, 10) を計算せよ。

本家:Problem 215 - Project Euler
日本語訳:Problem 215 - PukiWiki


第164問と同じような方法で解きました。

variee.hatenadiary.com

レンガの数の組わせは 2x+3y=32 の非負整数解として求められます。6組ありました。

 (x, y) = (1, 10),\, (4, 8),\, (7, 6),\, (10, 4),\, (13, 2),\, (16, 0)


この後の手順は次のとおりです。第164問を解いたときとくらべるとだいぶ楽でした。

  1. Permutations で2を x 個,3を y 個並べた順列を作る
  2. Accumulate で累積和を計算。レンガの区切り位置を並べた順列を作る。計算量を減らすため,末尾の32を削除
  3. 「a の上に b をおける」を「a->b」で表してグラフにする
  4. 隣接行列を計算。その9乗の成分の総和が答え