PEをMathematicaで

Project Eulerに挑戦してみよう

101-200

Project Euler 182 / RSA暗号

RSA暗号は以下のアルゴリズムにもとづいている。 鍵生成 二つの異なる素数 p と q を生成する n=pq とし,φ=(p-1)(q-1) (=φ(n)) とする 1 暗号化 平文を [0, n-1] 中の整数 m とする。平文は以下の方法で [0, n-1] 中の整数に暗号化される c=m^e mod n とし,…

Project Euler 183 / 分割した積の最大値

正整数 N に対して P=(N/k)^k (k >=2) の最大値を M(N) であらわす。M(N)が無限小数のとき D(N)=N とし,M(N) が有限小数のとき D(N)=-N とする。 5 ≦ N ≦ 100の とき,ΣD(N) = 24385 ≦ N ≦ 10000 のとき,ΣD(N) を求めよ。 本家:Problem 183 - Project Eul…

Project Euler 159 / 因数分解の数字根和

合成数は多くの異なった方法で因数分解することができる。たとえば 24 は 7 通りに因数分解される。 24 = 2x2x2x3 24 = 2x3x4 24 = 2x2x6 24 = 4x6 24 = 3x8 24 = 2x12 24 = 24 ある数の各桁の数字を足し合わせることを和が 10 未満になるまで繰り返したとき…

Project Euler 126 / 直方体層

3x2x1 の直方体の表面すべてを覆いつくすのに必要最小限の立方体の数は 22 個である。さらにこの立体に表面を覆いつくすように2層目を追加すると,46 個の立方体が必要である。3層目は 78 個,4層目は 118 個の立方体が必要である。ところで 5x1x1 の直方体…

Project Euler 106 / 特殊和集合:メタ検査

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

Project Euler 128 / 六角形タイルの差分

六角形のタイルを図のように反時計回りに置いていく。タイル n とそれに隣接するタイルのうち,書いてある数字と n の差が素数となるタイルの枚数を PD(n) と定義する。たとえばタイル8の場合,まわりのタイルの数字と8の差は 12, 29, 11, 6, 1, 13 となるの…

Project Euler 111 / 重複桁を持つ素数

重複した桁を含む 4 桁の素数を考える。 各桁に1は最大3個含まれ,このような素数は9つある。1117, 1151, 1171, 1181, 1511, 1811, 2111, 4111, 8111 n 桁の素数を考える。各桁に d が最大 M(n, d) 個含まれるとする。このような素数が N(n, d) 個あり,それ…

Project Euler 109 / ダーツ

問題の概要 ダーツをダブルアウト方式でプレイするとき,100点未満の状態からチェックアウトする方法は何通りあるか求めよ。 各回に得られる点数は1~20点の1倍(シングル),2倍(ダブル),3倍(トリプル)の他,ブルの25点,ブルのダブルの50点である。本…

Project Euler 107 / 最短ネットワーク

問題の概要 頂点数40の重みつき有向グラフgが与えられる。その最小全域木をg'とする。gの重みの総和とg'の重みの総和の差を求めよ。本家:Problem 107 - Project Euler 日本語訳:Problem 107 - PukiWiki 解法 頂点数7のとき WeightedAdjacencyGraph でグラ…

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) 型…