PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 297 / ゼッケンドルフ表記

すべての正整数はフィボナッチ数列の連続しない項の和で一意に表せる。たとえば 100=3+8+89 である。 このような表し方はゼッケンドルフ表記と呼ばれる。整数 n>0 に対して z(n) を n のゼッケンドルフ表記中の項数とする。z(5)=1, z(14)=2, z(100)=300Probl…

Project Euler 59 / XOR暗号解読

各文字はそれぞれ一意のコードに割り当てられている。よく使われる標準としてASCII (American Standard Code for Information Interchange) がある。ASCIIでは大文字 A = 65,アスタリスク (*) = 42,小文字 k = 107 のようにコードが割り当てられている。モ…

Project Euler 421 / n^15+1 の素因数

n^15+1 の形の数は n > 1 のすべての整数 n において合成数である。正の整数 n と m に対し,m を超えない n^15+1 の異なる素因数の和を s(n, m) とする。 2^15+1 = 3×3×11×331 s(2, 10) = 3 s(2,1000) = 3+11+331 = 345 同様に 10^15+1 = 7×11×13×211×241×2…

Project Euler 160 / 階乗の下位桁

任意の N に対して f(N) を N! の末尾の 0 の前にある最後の5桁とする。 9! = 362880, f(9)=36288 10! = 3628800, f(10)=36288 20! = 2432902008176640000, f(20)=17664 f(1,000,000,000,000) を求めよ。Problem 160 - Project Euler 下準備 2と5でどんどん…

Project Euler 272 / モジュラー立方数2

正の整数 n に対し,C(n) を 1n=91 のとき,x は 8 つの値を取りうる。9, 16, 22, 29, 53, 74, 79, 81 であり,C(91)=8 である。C(n)=242 をみたす正整数 n≤10^11 の合計を求めよ。Problem 272 - Project Euler 検算用の式を作る1 PowerModList を使うと C(…

Project Euler 224 / だいたい直角三角形2

三辺(a≤b≤c)がすべて整数の三角形で,三辺が次の式をみたしているものを"わずかに鈍角(barely obtuse)"と呼ぶ。周辺の長さが 75,000,000 以下のわずかに鈍角な三角形はいくつあるか。Problem 224 - Project Euler 第223問と同じ方法で解きました。variee.hat…

Project Euler 223 / だいたい直角三角形1

三辺(a≤b≤c)がすべて整数の三角形で,三辺が次の式をみたしているものを"わずかに鋭角(barely acute)"と呼ぶ。周辺の長さが 25,000,000 以下のわずかに鋭角な三角形はいくつあるか。Problem 223 - Project Euler Solve で整数解を求める まず,検算用を兼ね…

算チャレ第1021回を解いてみた

ある4ケタの整数があり,次のような性質を満たしています。(性質)各ケタの数字を並べかえて作ることのできる整数のうち最大のものから最小のものを引くと,もとの整数になる。例えば1345という数は「1, 3, 4, 5」の4つの数字で出来ていて,これらを並べ替…

Project Euler 512 / べき乗のトーシェント数の和

オイラーのトーシェント関数を φ(n) とする。とすると g(100) = 2007 となる。g(5*10^8) を求めよ。Problem 512 - Project Euler を使って f(n) の式を整理します。これは n が偶数のとき 0,奇数のとき φ(n) です。奇数について φ(n) の和を求めます。5分か…

Project Euler 451 / モジュラ逆数

数 15 について考えよう。15と互いに素となる15以下の正数は8個ある。1, 2, 4, 7, 8, 11, 13, 14 である。それらの数の15を法とするモジュラ逆数は 1, 8, 4, 13, 2, 11, 7, 14 である。 1*1 mod 15 = 1 2*8 = 16 mod 15 = 1 4*4 = 16 mod 15 = 1 7*13 = 91 m…

Project Euler 258 / ラグ付フィボナッチ数列

数列を以下のように定義する。 0 ≤ k ≤ 1999 に対して gk = 1 k ≥ 2000 に対して gk = g(k-2000) + g(k-1999) k = 10^18 に対して gk mod 20092010 を求めよ。Problem 258 - Project Euler 10^18 という大きな添字,20092010という大きな法をどうするかがポ…

Project Euler 268 / 少なくとも4つの異なる100未満の素数を因数に持つ数

少なくとも 4 つの異なる 100 未満の素数で割り切れる 1000 未満の正の整数は 23 ある。少なくとも 4 つの異なる 100 未満の素数で割り切れる 10^16 未満の正の整数はいくつあるか答えよ。Problem 268 - Project Euler まずは単純な場合を考えました。たとえ…

Project Euler 153 / ガウス整数の調べ上げ

ガウス整数とは a と b がともに整数の複素数 a + bi のことである。普通の整数もガウス整数である (b = 0 のケース)。 b ≠ 0 のガウス整数と区別するために,普通の整数を「有理整数」と呼ぶことにする。有理整数 n をあるガウス整数で割った結果がガウス整…

Project Euler 061 / 巡回図形数

三角数,四角数,五角数,六角数,七角数,八角数は多角数であり,それぞれ以下の式で生成される。三角数P3,n=n(n+1)/21, 3, 6, 10, 15, ...四角数P4,n=n21, 4, 9, 16, 25, ...五角数P5,n=n(3n-1)/21, 5, 12, 22, 35, ...六角数P6,n=n(2n-1)1, 6, 15, 28, 45…

Project Euler 157 / ディオファントス方程式 1/a + 1/b = p/10^n を解く

ディオファントス方程式 1/a + 1/b = p/10^n (a, b, p, n は正の整数で a ≤ b) について考える。 n = 1 のとき,この方程式は次の20個の解を持つ。1/1+1/1=20/10 1/1+1/2=15/10 1/1+1/5=12/10 1/1+1/10=11/10 1/2+1/2=10/10 1/2+1/5=7/10 1/2+1/10=6/10 1/3+…

Project Euler 95 / 友愛鎖

ある数の真の約数とは,それ自身を除く約数すべてである。たとえば 28 の真の約数は 1, 2, 4, 7, 14 である。220 の真の約数の和は 284 で,284 の真の約数の和は 220 となっており,二つの数が鎖をなしている。このため,220 と 284 は友愛数と呼ばれる。さ…

Project Euler 510 / 3つの接する円

円 A と B がお互いに,そして線分 L と異なる3点で接している。 円 C は A, B, L で囲まれた領域の内部にあり,3つすべてに接している。A, B, C の半径をそれぞれ rA, rB, rC としよう。0 S(5) = 4 + 4 + 1 = 9また,S(100) = 3072 が与えられている。S(10^…

Project Euler 479 / 増加する根

式 1/x = (k/x)^2(k+x^2) - kx の3つの解(実数か複素数)を a_k, b_k, c_k で表す。たとえば k = 5 のとき,{a5, b5, c5} はおよそ {5.727244, -0.363622+2.057397i, -0.363622-2.057397i} となる。1 ≤ p, k ≤ n をみたすすべての整数 p, k に対してとしよ…

Project Euler 118 / パンデジタル素数集合

1から9のすべての数字を使い,自由につなげることで 10 進数の数字を作り,複数の集合を作ることができる。 集合 {2,5,47,89,631} は面白いことにすべての要素が素数である。1から9の数字をちょうど1個ずつ含み,素数の要素しか含まない集合はいくつあるか?…

Project Euler 449 / チョコレートコーティングキャンディー

菓子職人のフィルはできたてのチョコレートコーティングキャンディーを作っている。それぞれのキャンディーの核は方程式 によって定義された回転楕円体の形をしている1ミリの厚さで1つのチョコレートを均一にコーティングするには,どれだけのチョコレートが…

Project Euler 240 / 上位のサイコロ

6面のサイコロ(各面は1から6)を5個振って,上位3個の合計が 15 となる場合は 1111 通りある。 いくつか例をあげる。 D1,D2,D3,D4,D5 = 4,3,6,3,5 D1,D2,D3,D4,D5 = 4,3,3,5,6 D1,D2,D3,D4,D5 = 3,3,3,6,6 D1,D2,D3,D4,D5 = 6,6,3,3,3 12面のサイコロ(各面は1…

Project Euler 214 / トーティエント鎖

φ をオイラーのトーティエント関数とする。つまり自然数 n に対して φ(n) を gcd(k,n) = 1 をみたす k(1 ≤ k ≤ n) の数とする。繰り返し φ を適用することで正の整数は段々値が減っていき,最後は1となる鎖を作る。たとえば5からはじめると 5,4,2,1 という数…

Project Euler 249 / 素数の部分集合和

S={2, 3, 5, ..., 4999} を 5000 より小さい素数の集合とする。要素の合計が素数となるような S の部分集合の個数を求めよ。最下位の 16 桁を答えとして入力せよ。Problem 249 - Project Euler 第250問(要素の合計が250で割り切れる部分集合の個数)とほと…

Project Euler 171 / 各桁の平方の和が平方数となる数を求める

正の整数 n について,f(n) を各桁の数字の平方の和と定義する。f(3) = 3^2 = 9 f(25) = 2^2 + 5^2 = 29 f(442) = 4^2 + 4^2 + 2^2 = 360 Problem 171 - Project Euler 10^20-1 個もの数についてまともに f(n) を求めるわけにはいかないので,漸化式を使って…

Project Euler 271 / モジュラー立方数1

正の整数 n に対し,S(n) を 1 S(91)=9+16+22+29+53+74+79+81=363S(13082761331670030) を求めよ。Problem 271 - Project Euler 組み込み関数の PowerMod で x^3≡1 mod n が解けるので助かりました。 さて,与えられた 13082761331670030 は2から41までの素…

Project Euler 266 / 擬似平方根

12の約数は 1,2,3,4,6,12 である。このうち12の平方根を超えない最大の数は3である。 整数 n に対し,その平方根を超えないような n の最大の約数を n の擬似平方根(PSR) と呼ぶことにしよう。PSR(3102)=47 である。p を 190 未満の素数の積とする。 PSR(p) …

Project Euler 139 / ピタゴラスタイル

(a, b, c)で各辺の長さが整数の直角三角形の三辺を表す。一辺の長さが c の正方形中に先ほどの三角形を4つ配置することが可能である。たとえば (3, 4, 5) 三角形は 5×5 の正方形に4つ配置される。このとき, 中央部に 1×1 の穴が空いている。また, 5×5 の正方…

Project Euler 501 / 8個の約数

24の約数は8個である。 1, 2, 3, 4, 6, 8, 12, 24 ちょうど8個の約数を持つ n 以下の自然の個数を f(n) としよう。 f(100) = 10, f(1000) = 180, f(106) = 224427 f(10^12) を求めよ。Problem 501 - Project Euler 8個の約数をもつ数は p^3, p^3 q, pqr(p, …

Project Euler 127 / abc-hit

n の根基 (radical) を rad(n) と書き,n の異なる素因数の積とする。 たとえば 504 = 2^3*3^2*7 より rad(504) = 2*3*7 = 42正整数の3つ組 (a, b, c) が abc-hit であるとは GCD(a, b) = GCD(b, c) = GCD(c, a) = 1 a a + b = c rad(abc) をみたすことであ…

Project Euler 233 / 円上の格子点

(0,0), (N,0), (0,N), (N,N) を通る円周上の格子点の個数を f(N) とする。f(10000) = 36f(N) = 420 をみたす正の整数 N (≤ 10^11)すべての合計を求めよ。Problem 233 - Project Euler 円の方程式はこうなります。これをみたす整数(x, y)が420個ある条件は,2…

Project Euler 110 / ディオファントス逆数2

次の等式で x, y, n は正の整数である。1/x + 1/y = 1/nn = 4 では 3 つの異なる解がある。 1/5 + 1/20 = 1/4 1/6 + 1/12 = 1/4 1/8 + 1/8 = 1/4 解の数が 4,000,000 を超える最小の n を求めよ。Problem 110 - Project Euler 第108問の類題です。解の個数が…

Project Euler 202 / レーザービーム

正三角形ABCの内側に鏡がはられている。各頂点にはレーザーが通れるような微小の穴がある。Cから入ったレーザーが内側の辺で11回反射し頂点Cから出て行く経路は2つ存在する。1つを下に示す。もう1つはこの逆である。1000001回反射し出て行く経路は80840通り…

Project Euler 142 / 完全平方数コレクション

x+y, x-y, x+z, x-z, y+z, y-z がすべて平方数となる整数の組 x > y > z > 0で, 最小の x+y+z を求めよ。Problem 142 - Project Euler 与えられた数を順に a^2, b^2, ..., f^2 とおいて x, y, z について解きます。 x=(a^2+b^2)/2=(c^2+d^2)/2 y=(a^2-b^2)/2…

Project Euler 133 / レピュニットの非因数

1のみからなる数をレピュニット数という。長さ k のレピュニット数を R(k) であらわす。 R(6) = 111111R(10^n) というレピュニット数について考える。R(10), R(100), R(1000) は 17 では割り切れないが,R(10000) は 17 で割り切れる。さらに,R(10^n) が 19…

Project Euler 105 / 特殊和集合:検査

大きさ n の集合 A の要素の和を S(A) で表す。空でなく共通要素を持たないいかなる 2 つの部分集合 B と C に対しても以下の性質が真であれば,A を特殊和集合と呼ぼう。 S(B)≠S(C); つまり,部分集合の和はすべて異なる B が C より多くの要素を含んでいれ…

Project Euler 132 / 巨大なレピュニットの素因数

1のみからなる数をレピュニット数という。長さ k のレピュニット数を R(k) であらわす。R(10) = 1111111111 = 11×41×271×9091 の素因数の和は 9414 である。R(10^9) の最初の40個の素因数の和を求めよ。Problem 132 - Project Euler 非常に大きな数が相手で…

Project Euler 130 / 素数桁レピュニットと同じ性質を持つ合成数

1のみからなる数をレピュニット数という。長さ k のレピュニット数を R(k) であらわす。 R(6) = 111111GCD(n, 10)=1 となる正整数 n について, 必ず正整数 k が存在し n が R(k) を割り切ることが証明できる。A(n) でそのような最小の k を表す。 A(7) = 6, …

Project Euler 83 / 経路の和:4方向

下記の5次の正方行列で左上のセルから出発して上下左右に移動し,右下のセルで終了する道を探索する。一番小さな道は下で赤で示されており,このときの合計は2297になる。いま, 31Kのテキストファイル matrix.txt には 80*80 の行列が書かれている。左上のセ…

Project Euler 129 / レピュニットの非整除性

1のみからなる数をレピュニット数という。長さ k のレピュニット数を R(k) であらわす。 R(6) = 111111GCD(n, 10) = 1 なる正の整数 n が与えられたとき,R(k) が n で割り切られるような k が常に存在することが示せる。A(n) をそのような k の最小のものと…

Project Euler 174 / 穴あき正方形の数え上げ

輪郭が正方形で,正方形の穴を持ち,縦にも横にも対称性をもつものをlaminaeと定義する。8個のタイルが与えられると,3x3の1x1の穴をもつlaminaしか作れないが,32個のタイルならば2つの異なったlaminaeが作れる。タイルの枚数を t で表すと,t=8 は L(1) 型…

Project Euler 203 / 無平方二項係数

二項係数 nCk は三角形の形に並べることができる(パスカルの三角形)。上から8行見るとパスカルの三角形は12個の異なる数を含む。1, 2, 3, 4, 5, 6, 7, 10, 15, 20, 21, 35である。任意の素数の二乗が n を割り切らないとき,「n は平方因子を持たない」と…

Project Euler 173 / 100万枚以下のタイルで何通りの穴あき正方形を作れるか

輪郭が正方形で,正方形の穴を持ち,縦にも横にも対称性をもつものをlaminaeと定義する。たとえば32個のタイルを使うと以下の二つの異なったlaminaeが作れる。100個以下のタイルを使うと41種類のlaminaeが作れる。100万個以下のタイルを使うと何種類のlamina…

Project Euler 66 / ディオファントス方程式

次の形式の2次のディオファントス方程式を考えよう。 x^2 - Dy^2 = 1たとえば D=13 のとき,x を最小にする解は 649^22 - 13×180^22 = 1 である。D が平方数のとき,正整数のなかに解は存在しないと考えられる。D={2, 3, 5, 6, 7} に対して x を最小にする解…

Project Euler 124 / 順序付き根基

n の"根基"(radical)は rad(n) で表し,n の素因数の積を意味する。たとえば 504 = 2^3 × 3^2 × 7より rad(504) = 2×3×7 = 421 ≤ n ≤ 10 に対して rad(n) を計算し, rad(n) を対象にソートする。rad(n) が同じ場合は n を対象にソートすると以下のようになる…

Project Euler 51 / 素数の桁置換

*3の第1桁を置き換えることで 13, 23, 43, 53, 73, 83という6つの素数が得られる。56**3の第3桁と第4桁を同じ数で置き換えることを考えよう。この5桁の数は7つの素数をもつ最初の例である。 56003, 56113, 56333, 56443, 56663, 56773, 5699356003はこのよう…

Project Euler 168 / 数の循環

自然数 142857 を考える。最後の桁 7 を一番前に持っていく,すなわち,右に循環させると 714285 を得る。714285 = 5*142857これは 142857 の珍しい性質を示している。右に循環させた数の約数になっている。10 Problem 168 - Project Euler nの一般形は? 10…

Project Euler 243 / 弾性

分子が分母より小さい正の分数を真分数と呼ぶ。任意の分母 d に対して真分数は d-1 個ある。たとえば, d = 12 では次のようになる。1/12, 2/12, 3/12, 4/12, 5/12, 6/12, 7/12, 8/12, 9/12, 10/12, 11/12約分できない分数を弾性分数(resilient fraction)と呼…

Project Euler 307 / チップの欠陥

ある工場では,製造するICチップ n 個あたり k 箇所の欠陥がランダムに生じる。一つのチップにつき複数の欠陥が生じ得る。3箇所以上の欠陥を持つチップができる確率を p(k,n) とおく。 p(3,7) = 0.0204081633...p(20,000, 1,000,000) を小数点以下10桁に丸め…

Project Euler 204 / 一般化ハミング数

ハミング数とはどの素因数も5以下であるような正整数のことである。小さい方から順に並べると次のようになる。 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 1510^8以下のハミング数は1105個ある。素因数が n 以下の正整数を type n の一般化ハミング数と呼ぶことにする…

Project Euler 549 / 階乗の整除性

10 が m! を割り切る最小の m は m=5 である。25 が m! を割り切る最小の m は m=10 である。n が m! を割り切る最小の m を s(n) とする。s(10)=5, s(25)=10 である。2 ≤ i ≤ n において Σs(i) を S(n) とする。S(100)=2012 である。S(10^8) を求めよ。Prob…