PEをMathematicaで

Project Eulerに挑戦してみよう

101-200

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 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 147 / 斜交平行格子内の長方形

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

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 153 / ガウス整数の調べ上げ

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

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 118 / パンデジタル素数集合

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

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 139 / ピタゴラスタイル

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

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 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 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 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 173 / 100万枚以下のタイルで何通りの穴あき正方形を作れるか

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

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 168 / 数の循環

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

Project Euler 136 / 単体差分

x, y, z を等差数列となるような正の整数とする。正の整数 n が n=20 と与えられたとき方程式 x^2 - y^2 - z^2 = n はただ一つの解を持つ。13^2 - 10^2 - 7^2 = 20100未満の n で方程式がただ一つの解を持つ n は25個ある。5000万未満の n で方程式がただ一…

Project Euler 190 / 加重積の最大化

Sm = (x1, x2, ..., xm) を x1 + x2 + ... + xm = m かつ Pm = x1^1 * x2^2 * ... * xm^m を最大にする m 項の正の実数の組とする。たとえば [P10] = 4112 である([ ]は実数の整数部分を取り出す関数)。2 ≤ m ≤ 15について Σ[Pm] を求めよ。Problem 190 - …

Project Euler 197 / 再帰的に定義された数列のふるまい

f(x) = [2^(30.403243784 - x^2)] /10^9 ([ ] は床関数)とし,数列 un を u0 = -1, u(n+1) = f(un) と定義する。n = 10^12 に対して un + u(n+1) を求めよ。小数点以下9桁で解答せよ。Problem 197 - Project Euler 多分,周期性があるんだろうなあと思ってプ…

Project Euler 144 / レーザーの多重反射

レーザー物理学では, "white cell"とはレーザー光線を遅延させるための鏡の装置のことである。光線はcellに入り,鏡で反射して最終的には飛び出す。white cell が楕円 4x^2 + y^2 = 100 の場合を考える。 −0.01 ≦ x ≦ +0.01 に対応する上部に穴が空いていて…

Project Euler 191 / 賞をもらえる文字列

ある学校では出席率が高く遅刻率が低い生徒に褒賞金を出している。3日連続で休むか2回以上遅刻した生徒は褒賞金を得る権利を失う。n日間の各生徒の出席状況を3進の文字列で表す。文字はL (late,遅刻),O (on time,出席),A (absent,欠席) である。4日間の…

Project Euler 135 / 同一差分

正の整数 x, y, z が等差数列として与えられたとき, x^2 - y^2 - z^2 = n がちょうど2個の解を持つような最小の正の整数は n=27 である。 34^2 − 27^2 − 20^2 = 12^2 − 9^2 − 6^2 = 27n=1155 は方程式がちょうど10個の解を持つ最小の値である。ちょうど10個…