PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 389 / 正多面体のサイコロ

1つの偏りのない四面体のサイコロを振り,出た目 T を記録する。 T 個の偏りのない六面体のサイコロを振り, 出た目の合計 C を記録する。 C 個の偏りのない八面体のサイコロを振り, 出た目の合計 O を記録する。 O 個の偏りのない十二面体のサイコロを振り, …

Project Euler 147 / 斜交平行格子内の長方形

3x2 の斜め線が引かれた格子には下図のように全部で37個の異なった長方形が存在する。3x2 より横にも縦にも小さい5個の格子(1x1,2x1,3x1,1x2,2x2)を考えると, それらに存在する長方形の数は以下のようになる。 1x1: 1 2x1: 4 3x1: 8 1x2: 4 2x2: 18 これ…

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 61 / 巡回図形数

三角数,四角数,五角数,六角数,七角数,八角数は多角数であり,それぞれ以下の式で生成される。三角数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, …