PEをMathematicaで

Project Eulerに挑戦してみよう

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 158 / 左隣の文字より辞書順で後になる文字がちょうど1個となる文字列の探査

26文字のアルファベットから3個の異なった文字を取ると,長さ3の文字列を作ることができる。例えば 'abc','hat','zyx' である。 この3つの例について調べると,'abc'は左隣の文字より辞書順で後になる文字が2個ある。'hat'では左隣の文字より辞書順で後に…

Project Euler 141 / 平方数でもある累進数 n の調べ上げ

正の整数 n を d で割った商と余りをそれぞれ q と r で表す。d, q, r を適当に並び替えたときに等比数列になる場合がある。たとえば58を6で割ると商が9で余りが4である。4, 6, 9は公比3/2の等比数列になっている。このような n を累進数と呼ぶことにする。…

Project Euler 166 / 十字

0 ≤ d ≤ 9 なる整数 d で埋められた 4x4 の格子がある。以下の格子ではそれぞれの行, 列の和が12であり,斜めの和も12である。 6 3 3 0 5 0 4 3 0 7 1 4 1 2 4 5 0 ≤ d ≤ 9 なる d で 4x4 の格子をそれぞれの行,列,斜めの和が同じとなるように埋める方法は…

Project Euler 207 / 整数分割方程式

いくつかの正整数 k は整数の分割式 が成り立つ。4^t, 2^t, k はすべて正の整数で, t は実数とする。最初の 2 つの分割は 4^1 = 2^1 + 2 と 4^1.5849625... = 2^1.5849625... + 6 である。t も整数である分割を完全と呼ぶ。m≥1をみたす m に対して P(m) を k…

Project Euler 151 / 規格寸法用紙 : 期待値問題

ある印刷屋では毎週16回の定期的な仕事がある。毎回,A5サイズの特殊な色校正用紙を1枚使う。月曜日の朝に主任はA1サイズの特殊紙が入った新しい封筒を開ける。彼はA1の紙を半分に切る。するとA2の紙が2枚できる。片方を半分に切るとA3の紙が2枚できる。以下…

Project Euler 103 / 特殊和集合:最適化(1)

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

Project Euler 90 / 2つの立方体の数字

立方体の6面それぞれに異なる数字(0から9)が書かれている。2番目の立方体も同様になっている。異なる位置に2つの立方体を隣りあわせることで様々な2桁の数を作ることができる。たとえば平方数である64も作ることができる。両方の立方体の数字をうまく選ぶ…

Project Euler 417 / 逆数の循環節その2

単位分数とは分子が1の分数である。分母が 2 および 5 の素因数だけからなるとき,その単位分数は循環節を持たないと考えられる。そのような単位分数の循環節の長さは 0 であるとしよう。1/n の循環節の長さを L(n) で表す。3 ≤ n ≤ 1,000,000 における ΣL(n…

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 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^…