Project Euler
Problem 132 - Project Euler 1のみからなる数(1, 11, 111, ...)をrepunitと呼ぶ。k桁のrepunitをR(k)で表すことにしよう。 さて、R(10) = 1111111111を素因数分解すると素因数は11, 41, 271, 9091であるから、素因数の総和は9414である。 R()の素因数のうち…
Problem 131 - Project Euler いくつかの素数pにはが立方数となるような自然数nが存在する。 例えば、p=19のとき、n=8であり、。 このような性質をもつ素数pに対するnは一意に定まる。また、100未満の素数に限るとこのような素数は4つしかない。 100万未満の…
Problem 130 - PukiWiki (A(n)についてはProblem 129を参照) 5より大きな全ての素数pに対し、A(p)はp-1を割り切る。例えばp=41のとき、A(41)=5であるが、5は40を割り切る。 また、少ないながらもA(n)がn-1を割り切るような合成数も存在する。はじめの5つを示…
Problem 129 - PukiWiki 1のみを並べて作った数(1, 111, 1111111, ...etc.)をrepunitと呼ぶ。また、k桁のrepunitをR(k)で表すことにしよう。例えば、R(6) = 111111。 10と互いに素である自然数nを考えたとき、R(k)がnで割り切れる、というようなkが必ず存在…
Problem 128 - PukiWiki 1から順に2, 3, 4,...と数字が書かれた六角形のタイルを中心から外側に向かって反時計回りに敷き詰めていく。周の開始は時計でいう12時の位置とする(詳しくはリンク先問題文中の図を参照)。 値nが書かれたタイルは6枚のタイルに囲ま…
Problem 188 - Project Euler 正整数aのbによる"超冪"，もしくは"テトレーション"をa↑↑bまたはbaと表現し，これを次のように再帰的に定義する．a↑↑1 = a a↑↑(k+1) = a(a↑↑k)よって例えば3↑↑2=33=27，3↑↑3=327=7625597484987，そして3↑↑4はおおよそ103.638334…
Problem 204 - Project Euler ハミング数とは5を超える素因数を持たない正整数のことである． 小さい方からいくつか示すと，1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15...がハミング数である． 10^8未満の正整数のうちハミング数は1105個ある．正整数のうち，nを超…
Problem 173 - Project Euler 正方形の輪郭と正方形の"穴"を持ち，縦横に対象なものをsquare laminaと呼ぶことにする．正方形のタイルを並べてsquare laminaを作成することを考えると，タイルを32枚ちょうど使うのであれば2種類のsquare laminaを作成できる…
Problem 187 - Project Euler 合成数とは少なくとも2つの素因数を含む数の事である．例えば，15=3×5，9=3×3，12=2×2×3などである． 30以下の数の中には素因数(異なる必要はない)を2つだけ含むものが10ある(4, 6, 9, 10, 14, 15, 21, 22, 25, 26)． n の範囲…
Problem 203 - PukiWiki まず例として8列目までのパスカルの三角形を考える． 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1ここには12個の異なる整数1, 2, 3, 4, 5, 6, 7, 10, 15, 20, 21, 35が含まれる． 任意の素数…
Problem 205 - PukiWiki 答を「0.abcdefgという形で入力せよ」とあったのでabcdefだけを入力すればいいのだと勘違いしてハマってた．馬鹿すぎる． 470ms．
Problem 145 - PukiWiki ある正整数nについてこれを反転したものをreverse(n)とする．例えばreverse(123)=321．ここで，n + reverse(n)の各桁が全て奇数であるような数を考える．例えば36は36+63=99で条件を満たす．このような数をreversibleな数と呼ぶ．例…
Problem 127 - PukiWiki 正整数nの素因数の積をrad(n)とする．また，二つの正整数x, yの最大公約数(greatest common divisor)をGCD(x, y)とする． ここで，次の条件を満たす3つの正整数(a, b, c)をabc-hitであると呼ぶ． GCD(a, b) = GCD(b, c) = GCD(a, c) …
Problem 126 - PukiWiki ブロックで作られた立体を覆い尽くすのに必要なブロックの個数を考える．例えば3×2×1の直方体の場合，22個のブロックにより覆い尽くすことができる． さらに，直方体を覆い尽くしてできた立体をもう一度覆い尽くすのに必要なブロック…
Problem 125 - PukiWiki 回文数 595 は連続する平方数の和で表すことができるという面白い性質を持つ: 6^2+7^2+8^2+9^2+10^2+11^2+12^2 1000 未満で連続する平方数の和で表せる回文数はちょうど 11 あり、その合計は 4164 である。正の整数の平方のみをこの…
Problem 124 - PukiWiki nの素因数の積をrad(n)とする．例えばrad(504) = 2*3*7 = 42である． ある範囲について求めたrad(n)を，rad(n)を第1キー，nを第2キーとしてソートする．このときソート結果のk番目にあるnの値をE(k)とする．例えば1≦n≦10についてrad(…
Problem 123 - PukiWiki Problem 120と同種の問題．n番目の素数をp_nとし，(p_n - 1)^n + (p_n + 1)^nをp_n^2で割った余りが10^10より大きくなる最初のnを求める． 27ms．素数の探索範囲は適当．
Problem 122 - PukiWiki さっぱり解ける気がしないので色々調べている過程でKnuthのpower tree methodというものの存在を知った．それでどうにか理解したものの残念なことにこの問題を単純なpower treeで解くことはできない． 結局Evaluation of Powers | CO…
http://odz.sakura.ne.jp/projecteuler/index.php?Problem%20121 袋の中に最初赤と青の円盤が1枚ずつ入っている．プレイヤーは1ターンに1枚ランダムに円盤を取り出し，色を記録して元に戻す．ターンが終了すると赤色の円盤が追加される． ゲーム終了時に赤い…
Problem 120 - PukiWiki (a-1)^n + (a+1)^n == r (mod a^2)とする．あるaについてnを変えることでrも変化するが，このときrの最大値をr_maxとする(例えばa=7に対しn=3の時r=42でありこれが最大値なのでr_max=42)．3≦a≦1000に対しΣr_maxを求めよ． 最初brute …
Problem 119 - PukiWiki 512は各桁の和(8)を3乗した値に等しい(8^3 = 512)． 各桁の和を何乗かするとその値になる性質を持つ数としては，他に614656 = 28^4などがある． この性質を持つ値を小さいものから並べた数列の第n項をa_nとする．またa_nは2桁以上の…
Problem 118 - PukiWiki 1 から 9 の全ての数字を使い、自由につなげることで 10 進数の数字を作り、複数の集合を作ることができる。集合 {2,5,47,89,631} は面白いことに全ての要素が素数である。 1 から 9 の数字をちょうど 1 個ずつ含み、素数の要素しか…
Problem 117 - PukiWiki Problem 116と同じような問題．今度は違う長さのタイルを混ぜて使った場合の合計パターンを求める．ユニットの長さは同じく50．また，タイルを入れないパターンもカウントする． これもProblem 114-116と同じように解けるのでもうほ…
Problem 116 - PukiWiki Problem 114, 115と似た様な問題．長さ50のユニットに長さ2，3，4のタイルを入れるパターンが何通りあるのかを求める．タイルの間は開いている必要はないが，最低1枚のタイルを入れる必要があり，違う長さのタイルを混ぜて使うことは…
Problem 112 - PukiWiki 134468のようにどの桁の数字も左の桁の値以上である数字をincreasing numberと呼ぶ．逆に66420のようにどの桁の数字も左の桁の値以下である数字をdecreasing numberと呼ぶ． そして，increasing numberでもdecreasing numberでもない…
Problem 113 - PukiWiki Problem 112に引き続いてbouncy numberに関連した問題． bouncy numberで無い数の割合は調べる範囲を広げるほど減っていって，例えば100万未満だと12951個で，10未満まで範囲を広げても27732個しかない． 探索範囲を1 googol(10)未満…
Problem 114 - PukiWiki 最低3の長さを持つブロックを長さ50のユニット内に入れる方法は何通りあるか，という問題．ブロック同士の間は最低でも長さ1分あける必要があり，使用するブロックの長さは異なっていてもいい． 紙使ってパターンを列挙して考えたら…
Problem 115 - PukiWiki Problem 114を難しくした問題．ユニットの長さをn，ブロックの最低長さをmとしたとき，ブロックの入れ方のパターン数をF(m, n)で表す． 例えばF(3, 29) = 67315といった具合で，F(3, 50)ならProblem 114の答えである． F(50, n)につ…
Problem 111 - PukiWiki あまり綺麗なやり方ではないけど思ったより簡単に答えが出た．720ms． ただgmp使ってる．gmpってPEのためにあるんじゃないかと思うくらいPEの問題解く際には使い勝手が良い．良すぎるので多倍長演算とか素数判定とか素因数分解とかの…
Problem 109 - PukiWiki ダーツの問題．正解者少ない割に簡単な問題だった． 222ms．ベクトルで計算するように工夫したらもっと早くできそう． あと実はProblem 108と110も答えは出てるんだけどやり方がひどすぎるのとさっぱり改善できないのでとりあえず後…
