PEをMathematicaで

Project Eulerに挑戦してみよう

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 349 / ラングトンの蟻

黒白いずれかで色づけされた正方形の規則的な格子上をアリが動く。 アリは上下左右のいずれかを向いており,次のルールにしたがって隣接する正方形へ移動する。 黒い正方形上にいる場合,その正方形の色を白に変えて反時計回りに向きを変え,1マス前進する …

Project Euler 516 / 5-スムーズトーシェント

5-スムーズ数とは最大の素因数が5を超えないような数のことである。ハミング数とも呼ばれる。オイラーのトーシェント関数 φ(n) がハミング数となるような,L を超えない数 n の値の和を S(L) とする。 S(100)=3728S(10^12) を求めよ。回答は 2^32 を法として…

Project Euler 613 / Pythagorean Ant

30*40*50の直角三角形内にアリがいる。このアリがランダムに方向を選んで直進するとき,斜辺に達する確率を求めて小数第10位まで答えよ。 本家:Problem 613 - Project Euler3辺の長さを3, 4, 5として考えます。三角形の頂点が O(0, 0), A(3, 0), B(0, 4) と…

Project Euler 215 / 亀裂のない壁

2x1 と 3x1 のレンガを使って壁を作る。 ただし,水平方向に隣接したレンガ間の隙間が上下の層にまたがってはならない。つまり,伝播亀裂(running crack)がないようにする。たとえば下図の 9x3 の壁は条件をみたしていない。赤線が伝播亀裂だからである。9…

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 624 / Two heads are better than one

コイン投げで表が連続して2回出るまでに M 回かかるとする。M が n で割り切れる確率を P(n) であらわす。 P(2)=3/5, P(3)=9/31 である。有理数 a/b と素数p に対して a≡bq (mod p) をみたす最小の自然数 q を Q(a/b, p) であらわす。たとえば Q(P(2), 109)…

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 607 / Marsh Crossing

Frodo and Sam need to travel 100 leagues due East from point A to point B. On normal terrain, they can cover 10 leagues per day, and so the journey would take 10 days. However, their path is crossed by a long marsh which runs exactly South…

算チャレ1036回を解いてみた

「算数にチャレンジ!!」さんの第1036回の問題を解いてみました。 2つの整数アとイがあります。アとイはともに1以上100以下の整数です。ア+イが偶数で,ア×2+イ×3 が5の倍数となるような(ア, イ)は何組あるでしょうか。 http://www.sansu.org/used-html…

Project Euler 293 / 擬似フォーチュン数

偶数の正整数 N は 2 の累乗であるか素因数がすべて連続した素数である場合,許容的と呼ぶ。最初の 12 個の許容的な数は 2,4,6,8,12,16,18,24,30,32,36,48 である。N が許容的であるとき,N+M が素数である最小の整数 M > 1 を N の擬似フォーチュン数(pseud…

Project Euler 315 / デジタルルート時計(2)

前回の記事の続きです。Sam と Max の表示コストをそれぞれ計算して差をとるかわりに,両者の差だけ計算します。variee.hatenadiary.com 桁ごとのコスト差 表示がないことをΦであらわします。ある桁の表示が a から b に変わるとき,Sam は「a→Φ→b」,Max は…

Project Euler 315 / デジタルルート時計(1)

Sam と Max は2個のデジタル時計を「デジタルルート(数字根)時計」に作り変えるよう依頼されている。 デジタルルート時計は数字根をステップごとに計算するデジタル時計である。時計に数字が与えられると,時計は数字を表示し,計算を開始する。たとえば,…

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…