プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=278 やっとfが計算できるようになった。道のりは遠そう。 fの計算が速くなった。でも、このfで計算したら一生かかりそう。 p = 2のときができた。なんで他はできない？ 元の計…

http://projecteuler.net/index.php?section=problems&id=42 三角数の判定は、 (n2 + n) / 2 = m n2 + n - 2m = 0 n = (-1 + √(1 + 8m)) / 2 だから、1 + 8mが平方数かどうか。 sqrtが使えるが、sqrtの引数は実数でなければならないので型変換する必要がある…

Problem 75 （前略）Lをワイヤーの長さとして、L ≤ 1,500,000が唯一つの辺の長さが整数の直角三角形を成すLの個数を求めよ。 http://projecteuler.net/index.php?section=problems&id=75 ピタゴラス数の生成式を使うと周の長さは a + b + c = 2lm(m+n) とな…

Problem 40 http://projecteuler.net/index.php?section=problems&id=40 こんないい加減な書き方でも意外と速い。実際にはリストを作っていないようだ。 s [] = "" s (p:ps) = (show p) ++ (s ps) mul :: [Char] -> [Int] -> Int -> Int mul s [] k = 1 mul …

Problem 74 145という数は各桁の階乗の和が145に等しいという性質がよく知られている： 1! + 4! + 5! = 1 + 24 + 120 = 145 恐らく169はあまり知られていないが、169に戻ってくる最も長い数のチェーンを生成する。このようなループは3つしか存在しないことが…

Problem 38 http://projecteuler.net/index.php?section=problems&id=38 nで分ける。そのとき左辺第一項をmとして、mの範囲が決まる。例えば、n=4なら、右辺は最初の2つは3桁で残りは2桁だから、 2m ≥ 100, 3m < 100 => 34 ≤ m ≤ 50 range n = if k < n then…

Problem 73 n/dという分数を考える。ここで、nとdは正の整数。n

http://d.hatena.ne.jp/inamori/20100122/p2 前回、上付き下付きを処理する秀丸のマクロを書いたが、それは2バイト文字が混じるとうまく動かなかった。秀丸のマクロは2バイト文字は2文字として扱うからだ。それを回避するには、まず1文字を取ってそれを$cと…

Problem 36 http://projecteuler.net/index.php?section=problems&id=36 再帰的に10進の回文数を求めて2進でも回文になっているか判定する。2進数の回文数は末尾が1でなければならない。 bin_rev 0 = [] bin_rev n = (mod n 2):(bin_rev (div n 2)) numerize…

φ関数といえば、nの約数に亘って和を取るとnになる、という定理があります。Pythonで書くとこんなイメージです。 n == sum(map(phi, filter(lambda d: n % d == 0, range(1, n + 1))))これを利用できないでしょうか。 1 + … + 100 にこの定理を適用すると、 …

Problem 33 http://projecteuler.net/index.php?section=problems&id=33 11の倍数はダメ。 is_cancellable (x, y) = f x y || f y x where f x y = (div y 10) == (mod x 10) && x * (mod y 10) == y * (div x 10)a :: [(Int,Int)] a = filter is_cancellabl…

Problem 72 n/dという分数を考える。ここで、nとdは正の整数。n

Problem 71 既約分数をn/dとしたとき、d ≤ 1000000の既約分数を大きさの昇順に並べたとき、3/7のすぐ左の分数の分子を求めよ。 http://projecteuler.net/index.php?section=problems&id=71 dは1000000より6小さい数から上になります。なぜなら、そうでない分…

Problem 31 http://projecteuler.net/index.php?section=problems&id=31 使う最大のコインが決まっているときの総額の作り方の場合の数の配列をリストにする。 ちょっとややこしくなるとなかなか書けない。

プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=277 231は出たのに、なんで1004064は出ないのよ。 どうも不定方程式のプログラムが間違っているらしい。 なんとか答は出た。不定方程式のコードは符号が違うとうまく動かない代…

http://projecteuler.net/index.php?section=problems&id=30 Problem 30 使う数字を選んで、その5乗和の数字をソートしたら元に戻ればOK。数字は重複組合せになる。これは組合せより少しコードが簡単になる。 import Data.Listrep_comb a 0 = [[]] rep_comb …

Problem 70 オイラーの関数φ(n)はn以下でnと互いに素な正数の個数を決めるのに用いられる。 （中略）興味深いことに、φ(87109) = 79180は、87109が79180の数字の順番を変えただけになっている。 1 < n < 107でφ(n)がnの数字の順番を変えただけになっていて、…

http://projecteuler.net/index.php?section=problems&id=29 重複を排除するためにsetを用いる。setの使用は次のように行う。 import qualified Data.Set as Sinsert s n = S.insert n s s = S.empty s2 = S.insert 1 s b = S.member 1 s2 s3 = S.delete 1 s…

Problem 68 "magic" 3-gon ringというものを考える。これは1から6の数で埋められており、各ラインは足すと9になる。 時計回りで考えて、外周のノードで最も小さい数を含む3つの数のグループをスタートとすると、各々の解は一意に記述される。 4つの総和9,10,…

http://projecteuler.net/index.php?section=problems&id=28 螺旋を1歩ずつ辿っていくとこう書ける。ただし、遅い。 n = 1001 next (x, y) | y >= 0 && y >= abs(x) = (x + 1, y) | x = abs(y) = (x, y + 1) | y = abs(x) = (x - 1, y) | otherwise = (x, y …

Problem 61 三角数、四角数、五角数、六角数、七角数、ハ角数はいずれも多角数で、以下の公式で生成される。 （中略）3つの4桁の数、8128,2882,8281は、3つの興味深い性質を持つ。 1. そのセットは循環的、すなわち、各々のかずの最後の2桁が次の数の最初の2…

Problem 25 http://projecteuler.net/index.php?section=problems&id=25 単に桁数を求めると遅いが、桁数は数列の前の項のそれと同じかそれより1大きいかなので、それを考慮すると速くなる。 -- number of digits of n is m or m + 1 num_digits n m = if n …

Problem 57 2の平方根は無限連分数で表せる。 √2 = 1 + 1/(2 + 1/(2 + 1/(2 + ...))) = 1.414213... これを最初の4回の展開すると、 1 + 1/2 = 3/2 = 1.5 1 + 1/(2 + 1/2) = 7/5 = 1.4 1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666... 1 + 1/(2 + 1/(2 + 1/(2…

http://projecteuler.net/index.php?section=problems&id=24 例えば、0〜3で10番目の順列を考える。先頭の数字を選ぶと残りは3!通りだから、9を6で割ると1で余りは3。同様に2!で割って1余り1。1!で割って1余り0。これで[1,1,1,0]というリストができる。そこ…