PEをMathematicaで

Project Eulerに挑戦してみよう

201-300

Project Euler 234 / 半分割可能数

整数n(≥4)に対して最大の素数(≤√n)を n の下位素数平方根(lower prime square root)とし,lps(n)であらわす。同様に最小の素数(≥√n)を n の上位素数平方根(upper prime square root)とし,ups(n)であらわす。lps(4) = 2 = ups(4), lps(1000) = 31, ups(1000)…

Project Euler 285 / ピタゴラス・オッズ

Albert は正整数 k を選び,さらに二つの実数 a, b を区間 [0,1] の一様分布からランダムに選ぶ。さらに和 (ka+1)^2+(kb+1)^2 の平方根を計算し,最も近い整数に丸める。結果が k に等しければ,彼は k 点を得る。それ以外は 0 点である。k=6, a=0.2, b=0.85 …

Project Euler 218 / 完全な直角三角形

a=7, b=24, c=25 の直角三角形について考える。この三角形の面積は84であり,完全数6と28で割り切れる。さらに, この三角形は原始(primitive)直角三角形である。つまり,gcd(a,b)=1, gcd(b,c)=1 をみたす。さらに,c は平方数である。以下の条件をみたす直角…

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

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

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 で整数解を求める まず,検算用を兼ね…

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 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 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 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 202 / レーザービーム

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

Project Euler 203 / 無平方二項係数

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

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 204 / 一般化ハミング数

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

Project Euler 235 / 等差等比数列

等差数列と等比数列を用いた次の数列を考える。 u(k) = (900-3k)r^(k-1)s(n) = Σ[k=1...n]u(k) とする。s(5000) = -600,000,000,000 をみたす r を求めよ。小数点以下12桁に四捨五入して解答を入力せよ。Problem 235 - Project Euler これは易しい。等差と等…

Project Euler 205 / サイコロゲーム

ピーターは4面のサイコロを9つ持っている。サイコロの各面には1, 2, 3, 4と書いてある。コリンは6面のサイコロを6つ持っている。サイコロの各面には1, 2, 3, 4, 5, 6と書いてある。ピーターとコリンはサイコロを投じ,出た目の合計を比べる。合計が多い方が…

Project Euler 267 / 億万長者

あなたに変わった投資の機会が与えられる。£1 の資産からはじめて固定した比率 f を選び, 資産の中でその比率を公正なコイントスに賭け, 1000 回繰り返す。賭け金は表のときは倍戻り,裏の時は失う。例えば f=1/4 のとき,最初のトスでは £0.25 賭け,表が出…

Project Euler 277 / 修正コラッツ列

整数の修正コラッツ列は値 a1 から始めて次のようにして得られる。an が 3 で割り切れるならば a(n+1) = an/3 これを大きな下ステップ "D" と表す。an を 3 で割った余りが 1 ならば a(n+1) = (4an + 2)/3 これを大きな上ステップ "U" と表す。an を 3 で割…

Project Euler 265 / 2進円

2^N の2進数の数字は時計回りに N 桁連続する数字すべてで網羅するように円状に並べることができる。例えば N=3 では回転を無視すると2つの円状の配置が可能である。最初の配置では時計回りの3桁の数列は 000, 001, 010, 101, 011, 111, 110, 100 である。そ…

Project Euler 250 / 250250

要素の合計が250で割り切れるような {1^1, 2^2, 3^3,..., 250250^250250} の空でない部分集合の個数を求めよ。最下位の16桁を答えとして入力せよ。Problem 250 - Project Euler 部分集合の個数は 2^250250 個。とても全部は調べられないので,漸化式を使って…

Project Euler 225 / トリボナッチを割り切らない数

数列 1, 1, 1, 3, 5, 9, 17, 31, 57, 105, 193, 355, 653, 1201 ...は T1=T2=T3=1 および Tn=T(n-1)+T(n-2)+T(n-3) によって定義される。27はこの数列の任意の項を割り切らないことが証明できる。27はこの性質を持つ最初の奇数である。この数列の任意の項を…

Project Euler 291 / Panaitopol素数

素数 p がある正の整数 x, y に対してをみたすとき,p を Panaitopol 素数 と呼ぶ。 5x10^15 未満の Panaitopol 素数はいくつあるか。Problem 291 - Project Euler 問題131とほとんど同じ方法で解けてしまった。x と y の最大公約数を g として x=gX, y=gY(…

Project Euler 216 / 2n^2-1 の形の素数

式 t(n) = 2n^2-1 (n>1)で表される数 t(n) について考える。最初の数個を挙げると 7,17,31,49,71,97,127,161 となる。 この中では 49 = 7*7 と 161 = 7*23 だけが素数でない。n ≤ 10000 では 2202 個の t(n) が素数である。n ≤ 50,000,000 で素数である t(n)…

Project Euler 239 / 場違いな素数たち

それぞれ 1 から 100 まで番号の書かれたディスクが一列に無作為に並んでいる。ちょうど 22 個の素数の番号のディスクが番号順の位置と異なる場所にある確率を求めよ。素数でない番号のディスクはどれも番号順の位置にあってもなくてもよい。解答は小数点以…

Project Euler 211 / 約数の2乗の和

正の整数 n に対して σ2(n) を約数の2乗の和とする。たとえばσ2(10) = 1+4+25+100 = 1300 Problem 211 - Project Euler 約数の2乗の和は DivisorSigma[2,n] で簡単に求められますが,平方数の判定で苦労しました。Mathematica には isSquareQ みたいな関数が…