プロジェクトオイラー http://projecteuler.net/index.php Q53. nCr(1≤n≤100)の100万を超える項の個数 ふつうにやると、こう。 from math import factorialdef combination(n, r): return factorial(n) / factorial(r) / factorial(n - r)N = 100 M = 100000…

昨日たまたま寄った書店でこの本を買った。C++テンプレートテクニック作者: επιστημη,高橋晶出版社/メーカー: ソフトバンククリエイティブ発売日: 2009/04/25メディア: 単行本購入: 16人 クリック: 224回この商品を含むブログ (54件) を見るテンプレートを使…

プロジェクトオイラー http://projecteuler.net/index.php Q51. 例えば、56○○3の○に同じ数字を入れる。このとき7つが素数になる。○はいくつでもよい。素数が8つになる最小の整数。 0〜9を○に入れたうちの8つ以上が素数なので、少なくとも素数が3つ連続するこ…

プロジェクトオイラー http://projecteuler.net/index.php Q48. 11 + 22 + ... + 10001000 こうすれば答えは出る。 N = 1000 print str(sum(map(lambda x: x ** x, range(1, N + 1))))[-10:]しかし、多倍長整数を使っているのが気に入らない。 下10桁しか使…

プロジェクトオイラー http://projecteuler.net/index.php Q44. 五角数のペアで和と差も五角数のときの最小の差 ペアでなく、差を見ていく。D = Pn+k - PnとしてDを固定すると、kは1からDで決められる数まで見ればよい。

プロジェクトオイラー http://projecteuler.net/index.php Q41. 1からnまでの数字を一つずつ使った整数のうち最大の素数 n = 8, 9なら必ず3で割り切れるから、7でやってみる。

プロジェクトオイラー http://projecteuler.net/index.php 順番に解いていくことは変わらないが、これからは、ピックアップして載せることにする。 Q40. 1から順に順に並べて作った小数の小数第n位をdnと書いたときに、d1 * d10 * … * d1000000 各桁を順に数…

Q29. abの形(2 ≤ a ≤ 100, 2 ≤ b ≤ 100)の整数の数 99*99=9801から重複する数を引く。 まず、aが2乗から6乗で表される整数に分ける（なるべく大きいべき乗に入れる）。そして、例えば4乗なら、a = c4として、a20 = c80、a72 = (c3)96などと、より小さい底で…

Q28. 1を原点にスパイラル状に自然数を1001*1001個並べたときの、対角線上にある数の和 右下：4n2-2n+1 左下：4n2 +1 左上：4n2+2n+1 右上：4n2+4n+1という数列になっているので、和を取って、さらに公式を使って総和を求めればよい。 N = 1001 n = N / 2 pr…

Q25. フィボナッチ数列で最初に1000桁になるのは何項目か これも一般項表示してやればすぐに出てくる。 from math import sqrt, logN = 1000 print int( (log(5) / 2 + (N - 1) * log(10)) / log( (1 + sqrt(5)) / 2)) + 1

プロジェクトオイラー http://projecteuler.net/index.php Q25. フィボナッチ数列で最初に1000桁になるのは何項目か Q26. 1〜1000の逆数で最も長い循環の周期は 10倍して割り算して余りを得る。これを繰り返して、同じ余りになるまでが周期。 Q27. n2 + an +…

Q24. 0〜9の並び替えからなる数を辞書順に並び替えたときの100万番目の数 最上位桁を決めると残りは9!=362880だから、 999999 ÷ 9! = 2 … 274239 ということは、最上位桁は2で決まりである。2を除いた数字で以下同じことを繰り返す。

Q14. コラッツ列が最も長い100万未満の自然数 まず、偶数で50万未満の場合、その2倍の数のほうが列が長いので考慮しなくてよい。 また、6n+4の形なら、2n+1→6n+4 また、6n+5の形なら、4n+3→12n+10→6n+5となるから、考慮しなくてよい。 また、6n+2の形なら、4…

プロジェクトオイラー http://projecteuler.net/index.php Q13. 与えられた100個の整数の和の上位10桁 Q14. コラッツ列が最も長い100万未満の自然数 Q15. 20×20のグリッドの左上から右下へのルートの数 ただの組合せ。 Q16. 21000の各桁の和 Q17. 1〜1000を…

プロジェクトオイラー http://projecteuler.net/index.php Q9. ピタゴラスの数の組合せで、和が1000ときの積 自然数m,nでm > nとして、 a = m2 - n2 b = 2mn c = m2 + n2 とできる（ただし、aとbの大小は任意）。 a + b + c = 2m(m + n) 2 これでかなり絞り…

プロジェクトオイラー http://projecteuler.net/index.php Q6. 100までの総和の自乗と自乗和の差 和の公式を使えばよい。 N = 100 print N * (N ** 2 - 1) * (3 * N + 2) / 12

プロジェクトオイラー http://projecteuler.net/index.php 切りがないので、素直に解いたものはまとめて載せるようにした。 数学的な考察のある解法は別途。 Q3. 600851475143の最大の素因数 Q4. 3桁×3桁で最大の回文数 Q5. 1〜20で割り切れる最小の自然数 Q…

プロジェクトオイラー http://projecteuler.net/index.php Q2. フィボナッチ数列の4000000を超えない偶数項の和。 from itertools import takewhiledef fib(): a, b = 1, 2 while True: if a & 1 == 0: yield a a, b = b, a + bN = 4000000 print reduce(lam…

Project Euler http://projecteuler.net/index.php 存在を知ってはいたが、見たことはなかった。 最初から解いていこうと思う。 まず、Pythonで素直に書く。できれば数学的に考察した解も書く。 Q1. 3か5で割り切れる自然数で1000より小さいものの和。 a = f…

ここ1ヶ月くらいだろうか。少し長く走ったり多少速く走ったりすると胸に違和感を覚えるようになった。三好池のときはなんとか完走したが、結局最後まで飛ばすことはできなかった。それから症状が悪化しているような。しょうがないので、2週間目安で走らない…

「数学ガール」はもう返してしまったので、あまり正確に覚えていないが、最後の章で分割数を取り上げていた。テトラは自力で数え上げたが、我々にはプログラミングがある。 分割数は、例えば3を自然数で分割すると、 [ 3 ], [ 2, 1 ], [ 1, 1, 1 ]の3通りあ…

Python2.6からFractionクラス（分数というか有理数）がライブラリに追加された。すなわち、昨日の日記のコードはFractionを使っているので、2.6以上でないと動かない。 ここでは、Python2.6に付属しているヘルプを見ながら、Fractionクラスの紹介をする。 コ…

さっきから、日記の上の検索ボックスが使えない。マウスをクリックしてもすぐにフォーカスを失う。素早く打てば1文字なら入力はできるが。 どうもはてなスターがらみのバグのようだ。 Firefox1.5はダメ。IE8はだいじょうぶ。

前回のべき和を求めるプログラムのアセンブリを見てみると、非常に複雑で時間がかかっていそうである。これなら、別のプログラムでべき和を求める公式を得たほうがいいのではないだろうか。それをPythonで求めてみた。 from itertools import * from fractio…

図書館で借りてほったらかしにしてあった（他の本を読んでいた）「数学ガール」を今日読み出した。数学ガール (数学ガールシリーズ 1)作者: 結城浩出版社/メーカー: SBクリエイティブ発売日: 2007/06/27メディア: 単行本購入: 58人 クリック: 1,055回この商…

n点の木の場合の数は、 T(2) = 1 T(3) = 3 T(4) = 16 T(5) = 125 T(6) = 1296 T(7) = 16807 T(8) = 262144 T(9) = 4782969 T(10) = 100000000となっている。これは明らかに、 T(n) = nn-2 である。 なぜこうなるかあれこれ考えてみたがわからない。しかし、…

Pythonでは、リストのようなオブジェクトは代入では参照になる。 a = [ 1, 2 ] b = a b[1] = 3 print a # [1, 3]copyを使うと成分をコピーする。 import copya = [ 1, 2 ] b = copy.copy(a) b[1] = 3 print b # [1, 3] print a # [1, 2]ただし、深いコピー（…

m点でn辺のグラフが連結である確率を疑似乱数を使って計算している。 今回は、PythonからC++に移植して少し工夫した。すると、速度が100倍になった。そこで、繰り返し回数を10万回にして、m=3200を追加した。疑似乱数が少し気になるが、この問題ではあまり気…

記事を上げたあとに、昨日のアクセスログを見たら、154 http://d.hatena.ne.jp/なんだろういったい。バグで新着ログにずっと入っていたとか。なにかの間違いがあったのだろう。

同じことを点の数25,50,100,200,400,800,1600で行った。少し工夫して速くしたコードは下。そして、連結である確率が0.5,0.9,0.99を通過するn/mをプロットした。このグラフで見る限り、連結である確率が一定のn/mはlogmの1次関数のようである。0.99なら、 n =…