euler
Problem 37 - Project Eulerd:id:mtsuyugu:20080815:1218805119 の prime.scm を利用しています。結構時間がかかりました。 (use srfi-1) (load "./prime.scm") (define (keta n) (let loop ((n n) (i 0)) (if (= n 0) i (loop (quotient n 10) (+ i 1))))) …
Problem 12 - Project Euler約数が 500 以上ある最少の数を求める問題です。d:id:mtsuyugu:20080815:1218805119 の prime.scm を利用しています。 (load "./prime.scm") (define (tri n) (/ (* n (+ n 1)) 2)) (define (p12) (let loop ((i 2)) (let* ((tri …
素数関連の問題は次の関数群を使うことにしました。prime.scm とでもしておきます。 (use util.stream) (define divisible? (lambda (n d) (= (modulo n d) 0))) (define square (lambda (x) (* x x))) ; n 以上の整数ストリーム (define (integers-starting…
Problem 32 - Project Euler39*186 = 7254 のように被乗数、乗数、積をつなげた 9 桁の数がパンデジタル数になる、積の和を求める問題。総当たりで解きました。9 桁のパンデジタル数に 2 カ所切り込みを入れて 3 つの数を作り、初めの 2 つの数の積が 3 つめ…
三角形の周辺長が p(cartesian-product を使って総当たりでチェックしているために時間はかかりますが答えは求まります。 (use srfi-1) (use util.combinations) (define (square x) (* x x)) (define (right-angle? t) (= (+ (square (car t)) (square (cad…
Problem 67 - Project Eulerx^n が n 桁の数になるような x はいくつあるかという問題。 10^n は n+1 桁の数だから n がどんな値であれ x が 10 未満は明らかです。あとは 9^n ですら n-1 桁になるような n が見つかるまで n をひとつずつ増やして題意を満た…
Problem 79 - Project Euler問題の本質は、集合の要素間の部分的な順序関係が複数与えられたときに要素全体の順序を見つける問題です。これを解くのはトポロジカルソートです。とはいっても、この問題を解くまでトポロジカルソートについては名前と何をする…
Problem 31 - Project Euler金額が 1, 2, 5, 10, 20, 50, 100, 200 のコインがあるときに 200 の作り方は何通りあるかという問題です。 (use srfi-1) (define kinds (list 200 100 50 20 10 5 2 1)) ; k 以下のコインを使って n を作る方法は何通りあるか（ …
Problem 59 - Project Eulerキーと平文との xor を取ることで作成された暗号をブルートフォースで解く問題です。キーは小文字のアルファベット 3 文字を平文の長さだけ繰り返したものです。 (use srfi-1) (use util.combinations) (define encrypted (list 7…
Problem 33 - Project Euler49/98 は 1/2 ですが、49/98 の 9 を消しても 4/8 = 1/2 になるという面白い性質を持っています。問題 33 は二桁の分母分子からなる 1 未満の分数で先の例のような分数をすべてかけたときの分母の値はいくつか？ というものです。…
Problem 81 - Project Euler80*80 の行列の左上から右下まで要素を辿っていったときの経路となった要素の和が最少になるときの値はいくつかを求める問題です。各要素の値を、ひとつ上とひとつ右の要素の値を比べて小さい方の値と自分自身の値の和に置き換え…
Problem 99 - Project Euler1000 個ある 基数とべき数のペア（ファイルの各行にコンマ区切りで列挙されている）からべき乗数のうち、最大になるものは何番目かという問題です。基数、べき数ともに大きな数なので、べき乗数で比較せずに対数で比較します。比…
Problem 57 - Project Euler2 の平方根を連分数で近似するとき、 1000 段までの近似値のなかで、分子の桁数が分母の桁数より多いものはいくつあるかという問題です。初めは桁数を求めるために (floor (+ 1 (/ (log n) (log 10))) としてましたが、n = 1000 …
Problem 53 - Project EulernCr ( 1 ≤ n ≥ 100, 1 ≤ r ≤ n ) で 1,000,000 を超えるものはいくつあるかという問題。n と r で 2 重ループにして足していけば良いだけです。こういう問題を loop を使わずに解けるようになりました。 (use srfi-1) ; permutati…
Problem 52 - Project Eulerx, 2x, 3x, 4x, 5x, 6x が全て同じ数字の組み合わせになる正数 x を求める問題です。 (use srfi-1) (use util.stream) (define integer (stream-cons 1 (stream-map (pa$ + 1) integer))) ; 14235 -> '(1 2 3 4 5) (define (digit…
Problem 26 - Project Euler循環小数 1/d (1
Problem 56 - Project Eulera 100^100 が普通に計算できるので簡単です。 ; 1234 -> 10 (define (sum-digits num) (let loop ((r 0) (n num)) (if (= n 0) r (loop (+ r (modulo n 10)) (quotient n 10))))) (define (p56) (let loop ((a 1) (b 1) (r 0)) (i…
Problem 55 - Project Eulerまた、簡単そうな問題を見つけました。10000未満の数で、回文数と元の数を足すことを50回繰り返しても回文数があらわれないような元の数はいくつあるかという問題。問題の詳細は日本語訳 [http:z.sakura.ne.jp/projecteuler/index…
Problem 28 - Project Euler 21 22 23 24 25 20 7 8 9 10 19 6 1 2 11 18 5 4 3 12 17 16 15 14 13こういう風に正の整数を螺旋状に 1001×1001 のサイズまで並べていったとき対角線上にある数の合計を求める問題。まず n (n>1) 週目の数字の並びを考えてみる…
Problem 42 - Project Euler[id:mtsuyugu:20080707:1215444841] で過去に解いた problem 22 とよく似た問題です。 アルファベットに A = 1, B = 2 ... と数を割り当てたものの合計が "SKY" = 19 + 11 + 25 = 55 のように三角数になる単語が与えられたファイ…
Problem 35 - Project Euler1,000,000 以下の素数の中で桁を回転させてできる数字がすべて素数(ex. 197, 719, 971) である数はいくつあるかという問題です。primes.txt にはリストの形で 1,000,000 以下の素数が列挙しています。添え字が素数の要素は値が 1 …
Problem 97 - Project Euler一気に飛んで problem 97。2,357,207 桁からなるメルセンヌ数でない素数 28433*2^7830457+1 の下 10 桁を求める問題。(expt 2 7839457) とするのではなくて、10桁を超えないように常に下10桁に対して 2 を掛けるようにはしている…
Problem 7 - Project Euler10001 番目の素数を求める問題です。SICP でストリームを勉強してから project euler に戻ってきたときに解いていたのですが、まだ書いていませんでした。 (use util.stream) (define divisible? (lambda (n d) (= (modulo n d) 0)…
Problem 45 - Project Euler三角数: Tn=n(n+1)/2 かつ五角数 Pn=n(3n-1)/2 かつ六角数 Hn=n(2n-1) をみたす数のうち 40755 の次の数は何かという問題です。三角数 Tn について n = 2k-1 を代入すると Tn = n(n+1)/2 = (2k-1)(2k-1+1)/2 = 2k(2k-1) = Hkが成…
Problem 36 - Project Euler1,000,000 以下の数で 10 進数、2 進数どちらで表しても、回文になる数(ex. 585 = 1001001001) の和を求める問題。 (use srfi-1) (use srfi-13) (define (palindromic? num radix) (let1 str (number->string num radix) (string=…
Problem 40 - Project Euler1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 ... のように正の整数の順番に並べた数列の n 番目の数を d_n としたときにd_1 * d_10 * d_100 * ... * d_1000000を求める問題。 (use srfi-1) ; 123 -> '(1 2 3) (define (number->list num) (let…
Problem 48 - Project Euler先の問題を眺めていたらラッキー問題を見つけました。1 (use srfi-1) (define (p48) (let1 n (iota 1000 1) (modulo ;(fold (lambda (x y) (+ y (expt x x))) 0 n) ;(apply + (map (lambda (x) (expt x x)) n)) (apply + (map exp…
Problem 22 - Project Eulerファイルに書かれた名前を数値に変換したものの重み付け総和を求める問題です。ファイル入力は初めてでしたが調べたらすぐ分かりました。他の言語と変わりません。ファイルハンドラ、ファイルポインタではなくてポートと呼ばれる…
解き貯めしていたものがなくなってきたので、過去に解いたものを振り返って改良してみました。 d:id:mtsuyugu:20080528:1211984870 d:id:mtsuyugu:20080705:1215227594 総和を求めるのに fold でもループでもなく apply を使ってみました。
Problem 34 - Project Euler各桁の数字の階乗の和ともとの数が等しい数の総和を求める問題。 (define (fact n) (define ht (make-hash-table)) (if (hash-table-exists? ht n) (hash-table-get ht n) (let loop ((i n) (m 1)) (if (= i 0) (begin (hash-tabl…
