PEをMathematicaで

Project Eulerに挑戦してみよう

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 を対象にソートすると以下のようになる…