プロジェクトオイラー http://projecteuler.net/index.php Q122. べき乗の計算はバイナリ法を使うと速いが、それより掛け算の回数が少ない方法があることがある。例えば、15乗。200乗までの掛け算の回数の総和。 これは、以前に考えた。 http://d.hatena.ne.…

プロジェクトオイラー http://projecteuler.net/index.php Q120. (a-1)n + (a+1)nのa2の剰余のnを振ったときの最大値をrmaxとすると、3 ≤ a ≤ 1000での∑rmax nが偶数・奇数で分けると、 (a-1)n + (a+1)n ≡ 2 (mod a2) (n : even) (a-1)n + (a+1)n ≡ 2na (mod…

プロジェクトオイラー http://projecteuler.net/index.php Q119. (5 + 1 + 2)3 = 512のように数字の和のべき乗が元の数になるもののうち小さいほうから30番目のもの これもやはり逆から考える。すなわち、ある数のべき乗を考えて、その各桁の総和が元の数に…

プロジェクトオイラー http://projecteuler.net/index.php Q118. 1〜9のすべての数字を使って、いくつかの自然数を作る。{2,5,47,89,631}のように、その全てが素数である組合せは何通りあるか。 1〜9の順列を発生させる。最後が4,6,8は不可。重複しないよう…

プロジェクトオイラー http://projecteuler.net/index.php Q114. 長さnの列を色々な長さのブロックで埋める。ただし、長さ2は不可、また2より長いブロックは並んではいけない。n=50のときのブロックの埋め方は何通りあるか。 長さnの埋め方をan、一番左のブ…

プロジェクトオイラー http://projecteuler.net/index.php Q113. 134468のように数字が上がっていく数を増加数、66420ような数を減少数と呼ぶ。どちらでもない数をバウンド数と呼ぶこととする。10100より小さい非バウンド数はいくつあるか。 例えば、134○○○…

プロジェクトオイラー http://projecteuler.net/index.php Q110. 1/x + 1/y = 1/n の解(x, y > 0)の個数が400万を超える最小のn 108とほとんど同じ。少し工夫した。 例えば、素因数分解したときに素数が2つというのはありえない。約数の個数が100として、2か…

プロジェクトオイラー http://projecteuler.net/index.php Q108. 1/x + 1/y = 1/n の解(x, y > 0)の個数が1000を超える最小のn (x - n)(y - n) = n2となるから、n2の約数を数えればよい。あとから見るように対象となるnは偶数だから、重複を考えて、約数は20…

プロジェクトオイラー http://projecteuler.net/index.php Q106. （省略） まず、同じ大きさの部分集合の対のみ考えればよい。n = 7として、集合の要素に番号0〜6を付け、部分集合を次のように表す：{ 0, 2, 4 }, { 1, 3, 5 }。このようにソートしておき、対…

プロジェクトオイラー http://projecteuler.net/index.php Q104. フィボナッチ数で、頭の9桁とお尻の9桁がともに1〜9を全て使っている最初の数の項番号 特に工夫する余地もないし、素直にPythonで組んでみたが、なかなか返ってこない。仕方がないので、はじ…

プロジェクトオイラー http://projecteuler.net/index.php Q100. 青いディスク15枚と赤いディスク6枚を用意して、ランダムに2枚取り出して両方青である確率は1/2である。このような組合せで最初に両方のディスクをあわせて1兆を超えるときの青いディスクの枚…

プロジェクトオイラー http://projecteuler.net/index.php Q94. それぞれの辺の長さが整数で、辺の差が1以内のものを「ほぼ正三角形」と呼ぶ。面積も整数になるもので、周囲の長さが10億以内の「ほぼ正三角形」の周囲の長さの総和 辺の長さをそれぞれ、a, b,…

プロジェクトオイラー http://projecteuler.net/index.php Q91. 原点と0≤x,y≤50に2点とって、直角三角形を作る。いくつ作れるか。 素直に点を打って、面積が正とある角が直角を条件に数え上げればよい。 from itertools import productdef is_positive_area(…

プロジェクトオイラー http://projecteuler.net/index.php Q88. k個の自然数の和と積が等しいとき、和積数と呼ぶ。kに対する和積数の最小値の2≤k≤12000での総和 この問題ではじめて正答数が3桁になった。いよいよ問題が難しくなってくる。 kでなく、和積から…

プロジェクトオイラー http://projecteuler.net/index.php Q83. 与えられた行列の左上から右下へのルートの総和の最小 左上からの最小和を調べていく。調べられたマスのうち、隣にまだ調べられていないマスがあるマスのうち最小のものを得て、その隣のマスに…

プロジェクトオイラー http://projecteuler.net/index.php Q78. nの分割数をP(n)とすると、P(n)が100万で割り切れる最も小さいn 分割数の求め方はWikipediaに載っている。 http://ja.wikipedia.org/wiki/%E6%95%B4%E6%95%B0%E5%88%86%E5%89%B2

プロジェクトオイラー http://projecteuler.net/index.php Q75. 直角三角形の周の長さで辺の組合せが一通りしかない200万以下のもの 辺の長さは既約なら、m2 - n2, 2mn, m2 + n2だから、周の長さL=2m(m+n)。L/2 = kml (m

プロジェクトオイラー http://projecteuler.net/index.php Q72. 分母が100万以下の0より大きく1より小さい既約分数の数 要するに、φ(n)の総和だが、φ(n)を一つずつ求めると時間がかかる。 a = [ (n, True) for n in range(N + 1) ]とする。タプルの最初がφ(n…

プロジェクトオイラー http://projecteuler.net/index.php Q71. 分母が1000000以下で3/7より小さくて最も近い分数の分母 求める分数をp/qとすると、3/7 - p/q = (3q - 7p) / 7qだから、3q - 7p = 1であるp,qを求めればよい。3(q-5) = 7(p-2)より、q = 7n + 5…

プロジェクトオイラー http://projecteuler.net/index.php Q69. n ≤ 1000000 でn/φ(n)が最大になるn n = pn1e1pn2e2…pnmemと素因数分解されるなら、φ(n)/n = (1-1/pn1)(1-1/pn2)…(1-1/pnm)だから、n = 2 * 3 * …。

プロジェクトオイラー http://projecteuler.net/index.php Q67. 与えられた三角形状に配置された数を上から辿ったときの総和の最大 上から順に数字に総和の最大をつけていく。 本当は再帰で書きたいがうまくいかない。

プロジェクトオイラー http://projecteuler.net/index.php Q66. ペル方程式 x2 - Dy2 = 1で最小の解xが最も大きいD≤1000 ここを参照した。この計算をするために、前に作った代数的数のクラスを少し拡張した。

プロジェクトオイラー http://projecteuler.net/index.php Q61. 8128 → 2882 → 8281 → 8128 みたいに2桁がしりとりになるように巡回して、6つで巡回、それが三角数から八角数の一つずつを取る、そのときの総和 あらかじめ多角数のリストを作ってから、有向グ…

プロジェクトオイラー http://projecteuler.net/index.php Q60. 5つの素数の2つ結合した整数がそれぞれ素数となる組で総和が最小のもの そのような4つの組を求めて、そこに1つ素数を組み合わせて成り立つかどうか調べていくが、総和が最小のものを見つけなけ…

プロジェクトオイラー http://projecteuler.net/index.php Q59. 暗号の3文字のキーを見つけて、その和を求めよ 3の剰余で分けて、それぞれで最も多いコードを探す。最初、それが'e'になるのかと思ったら、スペースだった。

プロジェクトオイラー http://projecteuler.net/index.php Q57. √2 = 1 + 1/(2 + 1/(2 + … を途中で打ち切ったとき、 1 + 1/2 = 3/2 1 + 1/(2 + 1/2) = 7/5 などとなる。 これを10万回行ったとき、何回分母より分子の桁が大きくなるか 分子をan、分母をbnと…