2010-01-01から1ヶ月間の記事一覧

Project Euler 22,23

Problem 22 http://projecteuler.net/index.php?section=problems&id=22 ファイルからテキストを読むにはreadFileを使う。 文字をアスキーコードにするにはChar.ordを使う。 switch文のようなcase式がある。 import Data.List import Charsplit_core buff []…

Project Euler 22,23

Problem 22 http://projecteuler.net/index.php?section=problems&id=22 ファイルからテキストを読むにはreadFileを使う。 文字をアスキーコードにするにはChar.ordを使う。 switch文のようなcase式がある。 import Data.List import Charsplit_core buff []…

ペル方程式(2)

ペル方程式の最小解を求めます。 x2 - Dy2 = 1 これを変形すると、 x / y = √(D + 1 / y2) となり、x / y は√Dの近似になっています。x, yが大きくなればなるほど√Dに近づいていきます。 √Dを連分数で表したとき、途中で打ち切ったものの内でペル方程式を満…

Project Euler 276

プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=276 格闘してるけど、なかなかできない。aが素数のときだけはできたけど。 方針変えたら割と簡単にできた。なんということもなかった。 スコア見ると6位か。 やっと速くなった…

Project Euler 21

http://projecteuler.net/index.php?section=problems&id=21 約数を求めるために、エラトステネスのふるい的に素因数分解する。 その前に配列の更新方法。 import Data.Arraya = array (1, 5) [ (n, 1) | n update a = a // [(2, 2)] main = print(update a)…

Project Euler 60

Problem 60 3,7,109,673という素数は極めて注目に値する。どの2つの素数を取ってどの順番で結合しても、その結果は常に素数である。例えば、7と109を取ると、7109も1097も素数である。この4つの素数の和は792で、この性質を持つ4つの素数の組で最小の和であ…

Project Euler 54

Problem 54 トランプのポーカーには(中略)。 プレーヤー1が勝つ手はいくつあるか。 http://projecteuler.net/index.php?section=problems&id=54 速度に問題はないので、どのようにすればきれいに書けるかを考えます。 上の役から順にあてはまっているかど…

Project Euler 18-20

Problem 18 http://projecteuler.net/index.php?section=problems&id=18 あえて全てのパスで和を求める。 三角形の数の並びは横のリストのリストにする。 まず、0〜16383の数を用意する。上から始めて、2で割って余りが0なら左下に進み、1なら右下に進んで2…

Project Euler 15-17

Problem 15 http://projecteuler.net/index.php?section=problems&id=15大文字のCを使ったら怒られた。 c n 0 = 1 c n m = ( (c n (m - 1)) * (n - m + 1)) `div` mn = 20 main = print(c (n * 2) n) Problem 16 http://projecteuler.net/index.php?section=…

Project Euler 275(3)

やっと出来た。 最後は14時間かかった。 メモリはせこい方法で節約。2行を1行分に圧縮。それから、Pythonではタプルより多倍長整数のほうがメモリを食わないらしい。最後に、簡単に求められる部分をあらかじめ求めておいて、その解は記憶しないようにして、…

Project Euler 14

http://projecteuler.net/index.php?section=problems&id=14 コラッツ問題。単に1から100万までの長さを求める。 next_collatz n | (mod n 2) == 1 = 3 * n + 1 | otherwise = div n 2collatz_length 1 = 1 collatz_length n = 1 + (collatz_length (next_co…

Project Euler 12,13

Problem 12 http://projecteuler.net/index.php?section=problems&id=12 素直にn(n + 1) / 2を素因数分解する。 m = 500 primes = 2:[3,5..]div_pow n p | mod n p /= 0 = (n, 0) | otherwise = (\(n, e) -> (n, e + 1)) (div_pow (div n p) p)factorize n (…

Project Euler 275(2)

土日から方針を転換してみたら、15次は正しい値が出た。しかし18次はメモリ的にも時間的にも無理そう。17次ならいけそうだけど。メモリを使わないようにするにはユニークな解を生成すればいいのだけれど、どうしてもそれができない。

Project Euler 12,13

Problem 12 http://projecteuler.net/index.php?section=problems&id=12 素直にn(n + 1) / 2を素因数分解する。 m = 500 primes = 2:[3,5..]div_pow n p | mod n p /= 0 = (n, 0) | otherwise = (\(n, e) -> (n, e + 1)) (div_pow (div n p) p)factorize n (…

Project Euler 53

Problem 53 (前略)1 ≤ n ≤ 100 でnCrの値が100万を超えるものは区別せずにいくつあるか。 http://projecteuler.net/index.php?section=problems&id=53 nCrの計算は、 nCr = nCr-1 * (n - r + 1) / r という漸化式で計算します。 from itertools import ima…

Project Euler 10,11

Problem 10 http://projecteuler.net/index.php?section=problems&id=10 200万までの素数を出さなければならない。 n = 2000000 is_prime n = all (\p -> mod n p /= 0) (takeWhile (\p -> p * p main = print(sum (filter is_prime [2..n-1]))ここでは素数…

Project Euler 52(2)

もっと攻める方法を取りましょう。桁を増やしていって、数字を数えてダメならそこは捨てるという方法です。 まず、1桁だけで考えます。最初の桁は1です。これを2倍、3倍すると、最初の方は、2,3,4,5,6となるはずです。分数で考えて、[1, 7/6)ならこうなるは…

Project Euler 275

プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=275 出題が寝ている最中1時で、4時半になぜか目が覚めて枕もとのネットブックで問題を見てみた。まだ3人しか解けていない。回らない頭でなんとか問題を理解して考えた。バラン…

Project Euler 52(1)

Problem 52 125874という数とその倍の251748は同じ数字から成っていて違う順序である。 2x,3x,4x,5x,6xがxと同じ数字から成る最も小さいxを見つけよ。 http://projecteuler.net/index.php?section=problems&id=52 同じ数字から成る、は数字にリストにしてソ…

TeX → HTML

連分数について書いていたら、数式を書くのが大変でやってられなくなった。 例えば、 anm+1 とHTMLで表示させるには、 <var>a</var><sub><var>n</var></sub><sup><var>m</var>+1</sup> と書かなければならない。上付きと下付きの処理をして、変数をTimes New Romanのイタリックにしている。こんな簡単な式でも大変だ…

連分数

連分数(continued fraction)は、 の形の分数のことを普通は扱うようです。しかし、分子が1でないものも連分数と呼びます。 連分数の略記法 上の連分数は、しばしば [a0; a1, a2, ...] と略記されます。 連分数の作り方 例えば、√3を連分数で表してみましょ…

Project Euler 9

素直に書くととても遅い。 n = 1000 m = div n 2 is_right_angle (a, b, c) = a * a + b * b == c * c product_t (a, b, c) = a * b * c triplets = [ (a, b, c) | a a + b + c == n && a main = print(map product_t (filter is_right_angle triplets))直積…

Project Euler 51(2)

元になる数は、3つ以上の桁で0〜2のいずれか同じ数字でなければならなかったのですが、それを判定するのではなく、そういう数を作りましょう。これは、1が3つ以上ある6桁の数は、最上位桁1と1が2つ以上ある5桁の数の結合と、最上位桁2〜9と1が3つ以上ある5桁…

Project Euler 51(1)

Problem 51 *3の最初の数字を置き換えて、9つの可能な値のうち6つ:13,23,43,53,73,83がすべて素数であることがわかる。 56**3の3番目と4番目を同じ数字に置き換えると、この5桁の数が10の生成される数のうち7つが素数になる最初の例である。これにより次の…

Project Euler 8

はじめて文字列が出てきた。文字列は文字のリストである。だから++で結合できる。 Prelude> "a" ++ "b" "ab"文字列を数に変えるには read を使う。ただし、 s = "12" main = print(read s)とするとエラーが出る。どうやらreadは返す値の型が決まっていないら…

Project Euler 50

Problem 50 41という素数は次のように連続した6個の素数の和で表せる: 41 = 2 + 3 + 5 + 7 + 11 + 13 これは最も長い連続した素数の和で100より小さい素数になるものである。 100万より小さい素数で最も長い連続した素数の和で表される数は? http://projec…

ラテン方格

「数学ガール ゲーデルの不完全性定理」を少しずつ読んでいる。数学ガール/ゲーデルの不完全性定理 (数学ガールシリーズ 3)作者: 結城浩出版社/メーカー: SBクリエイティブ発売日: 2009/10/24メディア: 単行本購入: 37人 クリック: 930回この商品を含むブロ…

Project Euler 274

おいおい、こんなに簡単にできていいのかよ。問題解く時間より、問題読む時間のほうが長かったような気が。 フォーラムで3番だけど、実際の順位は? 風呂に入ってもっといい方法を考えよう。 世界ランクトップに立つ。なんという幸運。もう二度とこんなこと…

reduceの挙動

混乱しそうになったので、調べてまとめてみる。 def f(x, y): print (x, y), return x + yという関数を定義して、 print reduce(f, range(3))とすると、 (0, 1) (1, 2) 3つまり、f(f(0, 1), 2)を計算している。 print reduce(f, range(3), 0)とすると、 (0, …

Project Euler 5 - 7

Problem 5 http://projecteuler.net/index.php?section=problems&id=5最大公約数を求める。Haskellには最初からlcmが用意されている。 main = print(foldl lcm 1 [ 1..20 ]) Problem 6 http://projecteuler.net/index.php?section=problems&id=6特に難しいこ…