Project Euler Problem 131 Prime cube partnership
二乗リストと三乗リストを作って、\(n^2 \times p=m^3-n^2=(m-n)(m^2+mn+n^2)\)だから\((m^2+mn+n^2)\)の因数が素数なのを数えていましたが、遅かったので解説をぐぐりました。上記式変形は悪手だった様子。
https://euler.stephan-brumme.com/131/
\(n^3+n^2p=m^3\)
\(n^3(1+\frac{p}{n})=m^3\)
三乗根を取って、
\(n\sqrt[3]{(1+\frac{p}{n})}=m\)
\(n\sqrt[3]{\frac{n+p}{n}}=m\)
三乗根の中は有理数でなければ等式が成り立たないので、
\(\sqrt[3]{\frac{a^3}{b^3}}=\frac{a}{b}\)である。
よって、
\(n \times \frac{a}{b}=m\)
\(a^3=n+p\)
\(b^3=n\)
\(p=a^3-n=a^3-b^3=(a-b)(a^2+ab+b^2)\)
pは素数なので、a-b=1、\(a^2+ab+b^2=p\)である。
a-b=1、a>bより、
a=b+1
\(p=a^2+ab+b^2=(b+1)^2+(b+1)b+b^2=b^2+2b+1+b^2+b+b^2=3b^2+3b+1\)
従って、\(p=3b^2+3b+1\)の形の素数を一覧する。
一重ループで100万まで回して数字を出しました。
Project Euler Problem 130 Composites with prime repunit property
Problem 130 「素数桁レピュニットと同じ性質を持つ合成数」
素数マップを作って、素数マップにない数は合成数と判定しました。で、P129で速くしたロジックで計算しました。
Project Euler Problem 129 Repunit divisibility
1のみで構成される数をレピュニットと言う。R(k)をレピュニットの長さで定義する。例えばR(6)=111111である。
GCD(n,10)=1の正の整数が与えられ、R(k)を割り切るnは必ず存在し、A(n)をそのような数のkの最小のものとする。例えばA(7)=6、A(41)=5である。
A(n)が10を超える最小のnは17である。
A(n)が100万を超える最小のnを見つけよ。
A(n)を100万から始めて、割り切れる数を下からインクリメントして探しました。kは、11%n、余りに11足してまた余りを求めて…で余りが0になるまで繰り返してレピュニットの長さkを求めました。随分遅かったです。
Project Euler Problem 128 Hexagonal tile differences
1の六角形のタイルは, 12時から反時計回りに配置された2から7の6個の六角形のタイルの輪に囲まれている.
8から19, 20から37, 38から61, , , といった新しい輪も同様にして加えられるものとする. 下図に最初の3個の輪を示す.
p_128.gif タイル n とそれに隣接するタイルについて, 差の値が素数となる個数を PD(n) と定義する.
例えば, タイル8では時計回りに 12, 29, 11, 6, 1, 13 となるので, PD(8) = 3 である.
同様に, タイル17では 1, 17, 16, 1, 11, 10となるので, PD(17) = 2 となる.
PD(n) の最大値は3であることが示せる.
PD(n) = 3 となるタイルを昇順に並べた数列では, 10番目のタイルは271となる.
この数列について2000番目のタイルを求めよ.
シャープペンシルでしゃかしゃか書いて、一層目、二層目、三層目…を二次元配列に計算。
んなんですが、メモリーが足らずにOSからkillられました。
ですので頭を絞って、ある層の一層前、一層後だけメモリーに展開してもチェックできるよね、こっちの方がスピード遅いけれどしょうがないか、と一晩かけて数字を出して通しました。
フォーラム見たらなななんと驚きの内容が(笑) くやしいのでしゃかしゃか書いていたら、あー、つながった、と。
それで3秒切りました。別途ネタバレページに書きます。
Project Euler Problem 127 abc-hits
n の根基 (radical) を rad(n) と書き, n の異なる素因数の積とする. 例えば, 504 = 23 × 32 × 7 なので rad(504) = 2 × 3 × 7 = 42 である.
正整数の3つ組 (a, b, c) が abc-hit であるとは
GCD(a, b) = GCD(b, c) = GCD(c, a) = 1 a < b a + b = c rad(abc) < c の4つの性質を満たすことである.
(5, 27, 32) は abc-hit である:
GCD(5, 27) = GCD(5, 32) = GCD(27, 32) = 1 5 < 27 5 + 27 = 32 rad(4320) = 30 < 32 abc-hit は非常に稀である. c < 1000 のときには31個しかなく, そのときの ∑c は 12523 である.
c < 120000 での ∑c を求めよ.
後で考えてみたら、これがABC予想の問題でした。もちろん、分からないので、コスモタイヒミューラー理論は使いませんでした(笑)
互いに素な整数の三組で絞って、下から計算しました。数字を通して、フォーラムを参考に3秒未満で動かしました。
Project Euler Problem 126 Cuboid layers
3 x 2 x 1 の直方体の表面全てを覆いつくすのに必要最小限の立方体の数は 22 個である.
p_126.gif さらにこの立体に表面を覆いつくすように2層目を追加すると, 46 個の立方体が必要である. 3層目は 78 個, 4層目は 118 個の立方体が表面を覆いつくすのに必要である.
ところで 5 x 1 x 1 の直方体への1層目も 22 個の立方体が必要である. 同様に 5 x 3 x 1, 7 x 2 x 1, 11 x 1 x 1 の直方体への1層目も全て 46 個の立方体である.
何層目かが n 個の立方体からなる直方体の数を, C(n) と定義する. C(22) = 2, C(46) = 4, C(78) = 5, C(118) = 8 となる.
154 は C(n) = 10 を満たす最小の n であることがわかる.
C(n)=1000 を満たす最小の n を求めよ.
一段目、
long long calcOne(long long a,long long b,long long c){
return (a*c*2)+(b*a*2)+(c*b*2);
}
二段目以降
long long calcTwoNext(long long a,long long b,long long c,long long k){
long long ret=(a*c*2)+(a*b*2)+(c*b*2)+(a*(k-1)*4)+(b*(k-1)*4)+(c*(k-1)*4);
ret+=(k-2)*4*(k-1);
return ret;
}
で愚直に並べて計算しました。フォーラム見たら、もっと速い方法が載っていました。
Project Euler Problem 125 Palindromic sums
回文数 595 は連続する平方数の和で表すことができるという面白い性質を持つ: 6^2+7^2+8^2+9^2+10^2+11^2+12^2
1000 未満で連続する平方数の和で表せる回文数はちょうど 11 あり, その合計は 4164 である. 正の整数の平方のみをこの問題では扱うため, 1=0^2+1^2 は含めないことに注意せよ.
回文数でありかつ連続する平方数の和で表せる, 10^8 未満のすべての数の合計を求めよ.
総当りで数字を出したのですが、通らなかったので解説をググりました。
kogelab::memo Project Euler Problem 125
「単なるブルートフォースなのだが、範囲が違うけど同じ数が出うることと、それを加算してはいけないことに1時間ハマって死にたい。何この凡ミス。」
はい。私もハマりました。それで数字を通しました…。
Project Euler Problem 124 Ordered radicals
n の"根基"(radical)は, rad(n) で表し, n の素因数の積を意味する. 例えば 504 = 2^3 × 3^2 × 7 であるから, rad(504) = 2 × 3 × 7 = 42 である.
rad(n) を 1 ≤ n ≤ 100000 でソートした場合, E(10000) を求めよ.
ドンキーにRADを計算して、C++のpairに格納してソートしていました。なんかフォーラムを見て速くしたような気も…。忘れてしまいました。
Project Euler Problem 123 Prime square remainders
pn を n 番目の素数とする. (p1 = 2, p2 = 3, ...) r を (pn - 1)^n + (pn + 1)^n を pn^2 で割った余りとする.
例えば, n = 3 のとき, p3 = 5 であり, 43 + 63 = 280 ≡ 5 mod 25.
余り r が 10^9 より大きくなる n の最小値は 7037 である.
余り r が 10^10 より大きくなる最初の n を求めよ.
余りが10^10なので割る数は5桁から、nが偶数の時r=2が続いたのでnは奇数のみ、で出しました。
フォーラムを見て、a^2で割るなら、a^2以上の項は割れるので、a^1未満の項が余りで出てくる、を参考にしました。
この辺りからフォーラムを参考に、3秒切りを目指しています。
Project Euler Problem 122 Efficient exponentiation
n^15を求めるのに最も単純な方法では 14 回の掛け算が必要である.
n × n × ... × n = n^15
しかし2進法を用いれば, 6 回の掛け算で計算できる.
n × n = n^2 n^2 × n^2 = n^4 n^4 × n^4 = n^8 n^8 × n^4 = n^12 n^12 × n^2 = n^14 n^14 × n = n^15
ところがたった 5 回の掛け算のみでも計算できる.
n × n = n^2 n^2 × n = n^3 n^3 × n^3 = n^6 n^6 × n^6 = n^12 n^12 × n^3 = n^15
m(k)を nk を求めるのに必要最低限な掛け算の回数と定義する. たとえば m(15)=5 である.
1 ≤ k ≤ 200 に対し, Σ m(k) を求めよ.
深さ優先探索で探索しました。随分遅かったので、一度に探索木を作るとき、ある数字がある階層なのを記録して、次に同じ数字が現れたとき階層を比較して、以前記録した階層より深い場合はそれ以上の探索を打ち切りました。
以前記録した階層より大きければ記録して、続いて探索しました。
Project Euler Problem 121 Disc game prize fund
袋の中に赤い円盤 1 枚と青い円盤 1 枚が入っている. ある賭けゲームにおいて, プレイヤーは円盤を 1 枚ランダムに取り出しその色を記録する. 各ターンの終わりに円盤は袋に戻され, 追加の赤い円盤 1 枚が袋に足され, そして次の円盤がランダムに取り出される.
プレイヤーはゲームをプレイするのに 1 ポンドを支払い, ゲーム終了時に青い円盤を赤い円盤より多く取り出していれば勝利する.
ゲームが 4 ターンプレイされたとすると, プレイヤーが勝利する確率はちょうど 11/120 となる. したがって, 胴元が赤字の見込みになるまでにこのゲームで勝ちに対して割り当てるべき賞金の最大は 10 ポンドとなるであろう. 支払いはすべてポンドの整数倍であり, またゲームをプレイするのに支払われたもともとの 1 ポンドを含んでいるため, 与えられた例では実際にはプレイヤーは 9 ポンドを獲得することに注意しよう.
15 ターンがプレイされるゲーム 1 回に割り当てられるべき賞金の最大を求めよ.
深さ優先探索で探索して、当たりの数を数えました。
Project Euler Problem 120 Digit power sum
(a-1)^n+(a+1)^n を a^2 で割った余りを r と定義する.
例えば, a=7, n=3 の時, r=42 である: 6^3 + 8^3 = 728 ≡ 42 mod 49. n が変われば r も変わるが, a=7 の時 r の最大値 rmax は 42 であることがわかる.
3 ≤ a ≤ 1000 において, Σ rmax を求めよ.
考えてみれば当たり前なんですが、プログラムを流したら周期があるので、それで切り上げました。
無限ループで流して、途中で停止させて出た数字で確認しました。改めて、合同式で考えればちゃんとしたプログラムになるはずです。
Project Euler Problem 119 Digit power sum
512 という数は興味深い数である. というのも, 各桁の和を何乗かしたものに等しくなっているからである: 5 + 1 + 2 = 8, 8^3 = 512 である. この特性を持つ他の数は例えば 614656 = 28^4 である.
a30 を求めよ.
遅かったので、解説を検索したら逆から求めていました。
べき乗数を作って判定する方法で求めました。
Project Euler Problem 118 Pandigital prime sets
要素がすべて素数のパンデジタルな要素は何パターンあるか、な問題でした。
1文字、2文字、3文字の素数に分ける
それぞれなんの文字を持っているか分ける
そもそもで、文字が重複していたらその素数は使えない。
0が入っていたら格納しないです。
で全探索しました。随分遅かった記憶です。
Project Euler Problem 117 Red, green or blue tiles
黒い正方形のタイルと, 2 ユニットの長さの赤のタイル, 3 ユニットの長さの緑のタイル, 4 ユニットの長さの青のタイルから選んで組み合わせて, 5 ユニットの長さの 1 列をタイルで敷く方法はちょうど 15 通りある.
長さ 50 ユニットの 1 列をタイルで敷く方法は何通りあるか.
単純な深さ優先探索だと遅かったので、メモ化しました。
Project Euler Problem 116 Red, green or blue tiles
5 個の黒い正方形のタイルの列を, 赤(長さ 2), 緑(長さ 3), 青(長さ 4)から選んで, この色のついた長方形のタイルでいくつか置き換える.
50 ユニットの長さの 1 列に並んだ黒いタイルを置き換える方法は何通りあるか. ただし複数の色を混ぜることはできず, 少なくとも 1 個は色のついたタイルを使うこと.
深さ優先探索で探索しました。
Project Euler Problem 115 Counting block combinations II
注意 : 問題114を難しくした問題である。
nユニットの列が、最小mユニットの赤ブロックを持っている。二つの赤ブロックは、少なくとも1つの黒ブロックで区切られている。
敷き詰め関数F(m,n)は列を敷き詰める場合分けの数を表す。例えばF(3,29)=673135、F(3,30)=1089155である。
m=3の時、n=30が敷き詰め関数が1,000,000を超えるもっとも小さな値である。
m=50の時、敷き詰め関数が初めて1,000,000を超えるnを求めよ。
mの値に従って、一度赤ユニットを置いたらmだけ数を進めて黒ユニットを置いて、次は赤か黒、と深さ優先探索で全探索しました。
3秒は切れなかったですが先に進めてしまいました。
Project Euler Problem 114 Counting block combinations I
長さ7のユニットの列に、最小3ユニットの赤いブロックがある。どんな二つの赤いブロックも、少なくとも一つの黒いユニットで区切られている。この場合、並べ方は17通り。
列が長さ50ユニットの場合、並べ方は何通り?
深さ優先探索で、赤いブロックと黒いブロックを並べて全探索しました。
Project Euler Problem 113 Non-bouncy numbers
増加数でも減少数でもない正の整数をはずみ数と呼ぶ、googol数\((10^{100})\)未満ではずみ数でないものの数を数えよ、な問題でした。
P112のフォーラムの解説を見て、数字の区切り位置が出せればいいんじゃん、と組み合わせの数を数えました。大概で忘れています…。
ベタで数えて、増加数でも減少数でもない数を1から数えて正答を出しました。
随分時間がかかりました。
Project Euler Problem 111 Primes with runs
もう素数を一覧して、何桁重複しているか数えて、マップに格納して、和を求めてしまいました。
随分時間がかかりましたし、メモリーもたくさん使いました。
Project Euler Problem110 Diophantine reciprocals II
次のxとyの等式で、nは正の整数である。
\(\frac{1}{x}+\frac{1}{y}=\frac{1}{n}\)
n=1260の時、113個の個別の解があり、このnは、異なる解の数が100を超える最小の数である。 異なる解の数が400万を超える最小のnは何か?
注 : この問題は問題108の難しいバージョンで、総当りより賢い方法が求められる。
とのことでしたので、P108を見返したところ、n(x+y)=(x*y)で解いていました。
Problem108のメソッドを持ってきて解の数が400万を超えるまでnを回す方法だと帰ってこないだろうなー、と。別の方法ないかなー、逆に解の数からnを求められないかなーと。
分からなかったので解説をググりました。3^14 = 4,782,979, 3^15 = 14,348,907、この辺りがきわだと書かれていました。素数は37まで使用する、と書かれていたので、2,3,5,7,11,13,17,19,23,29,31,37をリテラルで。
十二重ループで14乗まで当って、べき乗からnを求めて、nが400万より大きかったら解の数を求めました。しばらく帰ってこなかったのですが、途中まで出た数字が400万に随分近かったのでを試しで通してみたら通りました。
これは通った内に入らないです。厳しいです。掲示板を見て、解法をさらいます。
Project Euler Problem109 Darts
ダーツの問題で、100点未満からチェックアウト出来る場合分けは何通りか、の問題でした。
1-20、シングル、ダブル、トリプル、ブル(25)、ブルダブル(50)
を深さ優先探索で選んでいって、ダブルアウト(ダブルもしくはブルダブル)で終われるか、0未満になっているか、で探索を切り上げました。
Project Euler P108 Diophantine reciprocals I
分からなくて解説をググりました。 任意の正性数nは、素数p1,p2...の積で表せる。因子の数は\(d(m^{2})=Π(2si+1)\)で求められる、と書かれていたのでこちらの式で数字を出しました。
なんで? が分からないまま数字を出したので振り返りました。
\(\frac{1}{(n+r)}+\frac{1}{(n+s)}=n\)
計算して、
\(rs=n^{2}\)
約数の数は素数入門を見て素因数分解の結果のべき乗の数を足した数、と判明。
n=4の時、\(n^{2}=16\)
16の約数は1,2,4,8,16で
4+1=5 4+16=20 4+2=6 4+8=12 4+4=8 4+4=8
で、一番小さい因数と一番大きい因数から使っていくので、解の数は因数の数/2の切り上げ。
Project Euler P107 Minimal Network
すべての頂点が連結されるように適当な辺を除いて最適化出来る、最適化を最大にした時の節約量の合計を求めよ、な問題でした。
頂点を結ぶので、ダイクストラ法で最短距離求めて行けないかなーと鉛筆で書いたのですが、こりゃだめだ、と。
他のアルゴリズム使えないかなーとプリム法を試したら例解が通ったので問題を通しました。
Problem 106 Special subset sums: meta-testing
ルール1 : S(B)≠S(C) 部分集合の和は異ならなくてはならない。
ルール2 : もしBがCより要素数が大きければ、S(B) > S(C)でなくてはならない。 n=4から得られる25個の集合のうち、ルール1をチェックしなくてはならないのは1個だけ、n=7の場合は70個だけ、である、n=12の時、ルール1をチェックしなくてはならない集合の数は何個か? な問題でした。
何度か試したのですが数字が通らなくて。解説をぐぐってしまいました。
作られた二つの集合をソートして、B[i]とC[i]を比べて、全てB>CだったりB<Cならルール1をチェックする必要はない、な解説が見つかりました。
そりゃそうですが計算として足したほうが早くないかなーと思いつつ、数字を出して確認したら通ったので次の問題に取り掛かりました。掲示板を見て、実は何の話? を追いかけます。
Problem 105 Special subset sums: testing
ファイルに、数字が格納されています、特別和集合の列を特定し、集合の和を求め、集合の和を全て合計せよ、な問題でした。
P103で作った関数を流用して、ファイルの内容を判定して合計しました。
Project Euler Problem 104 Pandigital Fibonacci ends
両端がパンデジタルなフィボナッチ数は? な問題でした。単純に足していったら桁が足りないだろうと。
ですのでメモリーはもったいないですが、intの長い配列を作って、足し算する関数を作って足していき、両端がパンデジタルかどうか判定して返しました。
みにくい方法ですので、他に方法があるはずです。こちらもフォーラムの掲示板に張り付きます。
Problem 103 Special subset sums: optimum
条件 :
数列を、二つの、重複していない部分集合B,Cに分ける。
\(n+1 = {b,a_1+b,a_2+b,...a_n+b}\)で作れるっぽいけれども、違うよね、n=7の時の数列を文字列にして回答してね、な問題文でした。
じゃあ別の方法があるかなーと考えたのですけれども、思いつかなくて。解説をググりました。すると、\(n+1 = {b,a_1+b,a_2+b,...a_n+b}\)で作った数列から、+-幾つを足したり引いたりして探していました。
ですので6重ループでゴリ押しってしまいました。部分集合を作る関数は、二進数で作りました。正答の数字は出せましたが、フォーラムの掲示板を見てスマートな方法を考えます。
Project Euler Problem 102 Triangle containment
三角形の頂点がファイルに格納されており、原点を含む三角形の数を数えよ、な問題でした。
ゲームの当たり判定で行けないかな? と検索。点と三角形の当たり判定( 内外判定 )が引っかかりました。
三角形の内側に点がある時、点と各頂点を結ぶベクトルと各辺のベクトルの外積ベクトルは三つとも同じ方向を向く、三角形の外側に点がある時、外積ベクトルの向きは揃わない、だそうです。
ベクトルの外積の求め方が分からないので検索しました。 ベクトルの外積の定義、図形的な意味、微分の公式が引っかかったので実装。
向き(z成分)だけ分かればいいので、\(z=x_1*y_2 - y_1*x_2\)で外積のz成分だけ計算して、三つの計算結果の向きが揃っていたら原点を含む、揃っていなかったら原点を含まない、でカウントしました。
Project Euler Problem 101 Optimum polynomial
どうやってk=2,3,4...の時の式を求めるかなーと。こしょこしょ書いていました。すると、n連1次方程式で解けるなーと気づきました。
k=2、\(OP(2,n)=7n-6\)は、
k=1 : \(a+b=1\)
k=2 : \(2^1a+b=8\)
\(a+b=1\)
\(2a+b=8\)
a、bを求め、7n-6を求めました。右辺は生成関数\(n^3\)にkを代入した1,8です。
k=3、\(OP(3,n)=6n^2-11n+6\)は、
k=1 : \(a+b+c=1\)
k=2 : \(2^2a+2^1b+c=8\)
k=3 : \(3^2a+3^1b+c=27\)
\(a+b+c=1\)
\(4a+2b+c=8\)
\(9a+3b+c=27\)
から\(6n^2-11n+6\)と鉛筆で書き、これで出せるなーと。
n連1次方程式をプログラムで解く方法は? とインターネットで検索した所、ガウスの消去法が引っかかりました。
例解を鉛筆でガウスの消去法で解いて、解けたのでプログラムにし、例解を通しました。
例解を通したので、問題の生成関数\(u_n = 1 − n + n^2 − n^3 + n^4 − n^5 + n^6 − n^7 + n^8 − n^9 + n^{10}\)を解いてみて、数字が通りました。
間を空けてメモを書いているので曖昧なメモになりました。解いたらすぐにメモを残します。
Arranged probability Problem 100
If a box contains twenty-one coloured discs, composed of fifteen blue
discs and six red discs, and two discs were taken at random, it can be
seen that the probability of taking two blue discs, P(BB) =
(15/21)×(14/20) = 1/2.
The next such arrangement, for which
there is exactly 50% chance of taking two blue discs at random, is a box
containing eighty-five blue discs and thirty-five red discs.
By finding the first arrangement to contain over 10^12 = 1,000,000,000,000 discs in total, determine the number of blue discs that the box would contain.
箱の中に青いディスクが15個、赤いディスクが6個入っていて二回続けてディスクを取り出した時、取り出した両方のディスクが青の確率は\(\frac{1}{2}\)である。
次にこの確率が\(\frac{1}{2}\)になるディスクの数は、青が85個、赤が35個である。ディスクの総数が\(10^{12}\)を初めて超える場合の青のディスクの枚数を答えよ。
で、考えました。ディスク全部の数をALL、青のディスクをBLUEとすると、
\(\frac{BLUE}{ALL}*\frac{BLUE-1}{ALL-1} = \frac{1}{2}\) です。\(BLUE^2 - BLUE - \frac{1}{2}(ALL^2+ALL)\)で、二次方程式の解の公式\(\frac{1±\sqrt{b^2-4ac}}{2}\)より、BLUE=\(\frac{1±\sqrt{1^2-4*1*\frac{1}{2}(ALL^2+ALL)}}{2}\)で、\(\sqrt{1+2 x (ALL^2+ALL)}\)が整数になるALLを\(10^{12}\)からインクリメントして探しました。
すると随分帰ってこなくて。インクリメントじゃ駄目だなーと。分からないので調べました。するとペル方程式に帰着させる、と解説されていたので解説を読みました。
Arranged probability Problem 100
\(\frac{BLUE}{ALL}*\frac{BLUE-1}{ALL-1} = \frac{1}{2}\)
\(\frac{BLUE^2-BLUE}{ALL^2-ALL} = \frac{1}{2}\)
\(BLUE^2-BLUE = \frac{ALL^2-ALL}{2}\)
\(2BLUE^2-2BLUE = ALL^2-ALL\)
平方完成して、
\(\frac{1}{2}(2BLUE-1)^2 - \frac{1}{2}= \frac{1}{4}(2ALL-1)^2 - \frac{1}{4}\)
両辺に4を掛けて、
\(2(2BLUE-1)^2 - 2= (2ALL-1)^2 - 1\)
移項して、
\(-2 = (2ALL-1)^2 - 2(2BLUE-1)^2 - 1\)
\(-1 = (2ALL-1)^2 - 2(2BLUE-1)^2\)
\((2ALL-1)^2 - 2(2BLUE-1)^2 = -1\)
(2ALL-1)=X、(2BLUE-1)=Yと置き、
\(X^2 - 2Y^2 = -1\)
の形式のペル方程式。2ALL-1,2BLUE-1の形式なのでそれぞれ奇数。
上のページで、ペル方程式の次に漸化式が記述されているのですが、漸化式の求め方が分からなかったのでググりました。
こちらのページより、
\(\binom{X_{n+1}}{Y_{n+1}}=\begin{pmatrix}a & Db \\ b & a\end{pmatrix}\binom{x_n}{y_n}\)
a=Xの最小の値、
b=Yの最小の値、
D=Yの係数
だそうなので
\(\binom{X_{n+1}}{Y_{n+1}}=\begin{pmatrix}1 & 2 \\ 1 & 1 \end{pmatrix}\binom{X_n}{Y_n}\)
行列の掛け算は、
\(\begin{pmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{pmatrix} \binom{b_1}{b2}=\begin{pmatrix} a_{11}*b_1 + a_{12}*b_2 \\ a_{21}*b_1 + a_{22}*b_2 \end{pmatrix}\)
なので、
\(\begin{pmatrix} 1 & 2 \\ 1 & 1\end{pmatrix}\binom{X_n}{Y_n}=\begin{pmatrix}X_n + 2Y_n \\ X_n + Y_n\end{pmatrix}\)
\(X_{n+1}=X_n+2Y_n\)
\(Y_{n+1}=X_n+Y_n\)
を漸近式として出しました。これで\(X_n\)と\(Y_n\)から\(X_{n+1}\)と\(Y_{n+1}\)を計算しつづけます。
(2ALL-1)=X、(2BLUE-1)=Yと置いたので、
\(ALL=\frac{X+1}{2}\)
\(BLUE=\frac{Y+1}{2}\)
XとYは奇数なのでXとYが奇数の場合のみALLとBLUEを計算して、ALLが初めて\(10^{12}\)を超えた時のBLUEを計算して表示。試しで通した所、通りました。
間違いを書いていたらごめんなさい。以上メモです。
Project Euler P99 Largest exponential
大きな数をそのまま掛けられないだろうなー、と。大きさを比べるだけなら対数取って比べるのはどうかな? と2を底にした対数を取りました。
対数法則により、(lg a^b = b*lg a)なので計算して、一覧の数字を比べました。
Project Euler P98 Anagramic squares
アナグラムの問題でした。最初、文字を入れ替えて意味のある言葉=アナグラムになるのをどうやって判定したらいいのかなーと。問題を読み返したらアナグラムはすべてファイルに含まれている、と書かれていたので、ファイル内のワードでアナグラム判定。
next_permutationで入れ替えて探していたのですけれど時間がかかって。思いついたら、ワード内の文字列を辞書順でソートして同じならアナグラムです。それでアナグラムを判定してリストに格納してリストをマップに格納しました。
これに数字を当てはめて、両方共平方数のを探す処理を書きました。平方数判定するのに予め平方数をマップに格納。後は数字の当てはめです。
0,1,2,3,4,5,6,7,8,9をnext_permutationで入れ替えて、文字数分左から取って総当りしました。プログラムを流したら同じ数字が並びました。重複して処理しているのでした。例えば四文字取る際に、1,2,0,4,5,6,7,8,9と1,2,0,4,9,8,7,6,5、です。
3文字の数字列、4文字の数字列...と前もって作ろうかなーと思いながら流しました。数字は出たので、これで通らなかったら数字列を前もって作ろうと確認したら正答で通ったのでそのまま次の問題に進みました。
より早く出来るよなー、です。
Project Euler Problem 97 Large non-Mersenne prime
28433×27830457+1 の下10桁を答えよ、な問題でした。
200万桁を超えるそうで、そのまま計算は出来ないだろうと。0が10個の数で割った時の余りに2をかけ続けて、28433をかけて1を足して正答の数字が出せました。
Project Euler Problem 96 Su Doku
数独の問題でした。数独のルールが分からないのでWikiPediaで調べました。 縦と横に同じ数字が現れてはならない、3x3のマスの中に同じ数字が現れてはならない、0に数字を埋めよ、な問題でした。
WikiPediaに解法が載っていて、既に埋まっている数字の横と縦には同じ数字はこないので、それで縦一直線、横一直線をその数字を借り埋めして、空いているマスが一つならそこで確定、だそうでした。
まずは上のロジックを実装しました。帰ってこなくて、盤面を見たら3x3のマスの中で0が一つ埋まっていない所で無限ループに入っていました。0が一つなら残りの数字で埋められます。埋めました。 多分3x3のマスの中で0が2個以上なら分岐して探索しないといけないだろうなーと思っていた所、0が2個以上で解けなくて帰ってきました。ですので3x3のマスの中で0を数えて総当りで埋めて探索。なかなか帰ってきませんでした。
ぼんやりと解いている盤面を見たり、解けた盤面判定のメソッドを書いていたら、横一行は1-9が一度だけ現れる行、縦一列も1-9が一度だけ現れる列で解かれていると気づきました。
ですので、3x3のマスに注目する方向から転換し、横一行に注目する方向に。一行目から見て、0の場所と、埋まっていない数字を一覧。縦に同じ数字がない組み合わせで仮決め。他にも埋められる組み合わせがあるかもしれないので再帰で分岐。Grid3、Grid4と埋められたのですが、時間がかかって。
ありえない埋め方に突き当たったらその線はないので、再帰を打ち切ろうと。まず、3x3のマスに注目して0を埋められる組み合わせが一つも見つけられなかったら詰んでいるのでその探索は打ち切り。 また、3x3のマスに同じ数字が入っていたらこちらもルールに則っていないので探索を打ち切り。
そんなロジックを組んで、何十分か流していたらGrid50まで通りました。左上の数字を三桁の数字に変換して合計。試しで答え合わせをしたら通りました。
振り返ると、全探索と枝刈りをやっていたのでした。チーター本や蟻本で読みましたが、自分が実際にやってみると骨だなー、と。
また、探索を打ち切るメソッドのスピードを早くしたり、探索を打ち切る判断を賢くすればさらにプログラムが早くなるでしょう。精進です。
Project Euler P95 Amicable chains
友愛鎖で、要素が1,000,000を超えない鎖で最長の鎖の最小のメンバーを返せ、な問題でした。
友愛数を求めるので、素因数分解じゃなくて因数の一覧だなー、とドンキーにループで割って友愛数を計算する関数を作成。
鎖を下からドンキーに1,000,000まで計算。途中で1,000,000を超える鎖なら次の数に。 計算したところ、帰ってこない数字が。見たら途中でループしていました。マップでループを検知して次の数字に。
途中で随分長い鎖が出てきて、これかなーと眺めていたのですがドンキーに999,999まで計算しました。結局、途中で出てきた長い鎖の最小のメンバーで試したら通りました。
次は数独です。数独のルールがそもそもわからないなー、と数独のルールを眺めています。まずは手でやって、それからプログラムに落とし込みます。以上メモです。
Project Euler P94 Almost equilateral triangles
最初問題文を読んだとき、1万人を切るような難しい問題かな? P93の次だから飛ばされたのかな? と。周囲が1,000,000,000までなら3で割って、とループの上限を設定。
1引くのと1足すので計算。それぞれ面積を計算。浮動小数点の計算怖かったのでなるたけ近い数字で計算するように、とヘロンの公式で計算して整数になるか判定して集計。通りませんでした。
ドンキーに底辺を1/2して、三平方の定理で三角形の高さを求めて三角形の面積を計算して整数になるか判定して集計しても通らなかったのと、ヘロンの公式を使ったのと結果が違いました。
計算ミスしてるかなー、そちらを追うかなーと思ったのですが、そもそもで浮動小数点怖い、と。整数で計算する方に倒しました。
で判定して数えました。特に二乗マップの生成で時間がかかりましたが、正答の数字は出せました。以上メモです。
Project Euler P93 Arithmetric expressions
1万人切りだから難しいだろうなーと。問題文を読んでわからなかったのでアイディアを書き出しました。 カッコの組み合わせを書き出して。これリテラルで行けないかな...? とリテラルで行くことに。
(1 2) 3 4
(1 2 3) 4
((1 2) 3) 4
(1 (2 3)) 4
的にリテラルで。((1 2 3) 4)的に数字が三つ以上並ぶ場合は*,/を優先して+,-を後回しに。
1,2,3,4から6,7,8,9までの数字列を四重ループで作成。next_permutationで順列を総当りして計算。
計算してみたら、同率が二つ。二つの数字を試したら片方が通りました。通りましたが通った内に入らないだろうと見直し。
問題文に帰って考えました。
14 = 4*(3 + 1 / 2)
ですが、1/2で0.5になっています。3.5 x 4=14。途中で小数になったら例外を投げて次の計算に飛ばしていましたが、途中で小数になっても最後に整数になる場合もありました。
ですので途中で小数になっても中断せずに計算し、結果が整数だったら結果マップに格納。それで正答が出せました。メモです。
Project Euler Problem 92 Square digit chains
1から1000000までループを回して、それぞれの数字の各桁を文字列に直して各桁を二乗して合計。再帰して、1になったらfalse、89になったらtrueを返してカウントしました。
Project Euler Problem 91 Right triangles with integer coordinates
三角形の三つの頂点の内、一つの頂点を(0,0)で固定。他のp1(x1,y1),p2(x2,y2)の座標を、四重ループで総当り。
二点の距離から三辺を求めました。√(xa-xb)^2+(ya-yb)^2ですが、ルートを取ってdoubleになるのが嫌だったのでルートは取らずに。
一番長い辺を判断して、三平方の定理により一番長い辺の長さの二乗=他の辺その1の長さの二乗+他の辺その2の長さの二乗 だったら直角三角形と判断。
p1(x1,y1),p2(x2,y2)がひっくり返っているのを重複して数えたので最後に2で割りました。
Project Euler Problem 90 Cube digit pairs
題意がわからなったのでググりました。0-9の数字を二つの六面体サイコロに割り当てて、平方数をすべてカバーできる数の割当て数を算出せよ、な問題のようです。
9 x 9=81,10 x 10=100なので、出す平方数は81まで。01,04,09,16,25,36,49,64,81。
サイコロが二つなので12重ループでゴリ押してしまいました。再帰でもっと良い方法があるでしょう。
6だけ含まれている場合9を、9だけ含まれている場合6を列に加えました。
二つのサイコロの数字列から、01,04,09,16,25,36,49,64,81が全部作れるか判定。
また、例えば
サイコロ1 1,4,5,7,8,9
サイコロ2 0,2,3,6,7,8
の場合と、
サイコロ1 0,2,3,6,7,8
サイコロ2 1,4,5,7,8,9
の場合の両方をカウントしてしまったので、最後に2でカウント数を割りました。もっと賢い方法がありそうなので掲示板を見ます。
Project Euler Problem 89 Roman numerals
わからなかったので、ファイルに記載されているローマ数字(文字列A)を10進数にして、10進数からローマ数字に変換(文字列B)して、文字列Aと文字列Bの差を合計しました。
Product-sum numbers - Problem88
わからなかったので検索して、ある数nからkを求めて、kに当てはまる最小のnを一覧しましょう、ってなページを見ました。
なので素数一覧を作って、素数でない数を下から12000までいちいち素因数分解して、素因数分解した一覧の組み合わせを再帰で全部出してkに当てはまる最小のnを計算してみたら長い時間かかっても終わりませんでした。
なので諦めて14重ループでゴリ押しました。答えの掲示板を見ると何ミリ秒で終わったよ、なコードが載っているので、説明を読んでコンパイルしてロジックを追います。