問題16: 2^1000 の各桁の数字を合計した値を求めよ。[=>問題文] bigint ライブラリの改良 かなりヘビーな計算量になりそうなので、問題13で作った多倍長整数ライブラリの改良と、機能追加をします。改良点は２つ。まず、多倍長数をあらわすリストの要素を0〜…

問題15: 20x20のマトリクスにおいて左上端から右下端へ格子を通って到達する経路は何通りあるか。ただし、左から右、上から下へしか移動できないものとする。[=>問題文] 図を描いてみる 簡単な図を書くだけですぐに仕組みが分かります。 右から左、下から上…

問題14: 100万未満の数の中でコラッツ数列がもっとも長くなる数を求める。[=>問題文] 最初の10個を書いてみると。 1 (1) : 1 2 (2) : 2 - 1 3 (8) : 3 - 10 - 5 - 16 - 8 - 4 - 2 - 1 4 (3) : 4 - 2 - 1 5 (6) : 5 - 16 - 8 - 4 - 2 - 1 6 (9) : 6 - 3 - 10 …

問題13: 提示された50桁の数字100個の総和の上位10桁を求める。[=>問題文] とうとうこの手の来てしまいましたね。多倍長演算ってライブラリや言語サポートがないとめんどくさいんだよな・・・。足し算だけなので最低限機能でサクっといきましょう。 問題13の…

問題12: 501 個以上の約数をもつ最初の三角数はいくらか。[=>問題文] 問題12の解答 (defun factorize (N) "素因数分解" (let ((n N) (i 1) (dest nil)) (if (zerop (mod n 2)) (let ((count 0)) (while (zerop (mod n 2)) (setq n (/ n 2)) (incf count)) (s…

問題11: 提示された20x20の数方陣において縦横斜め連続する4つの数字の積で最大のものを求めよ。[=>問題文] 一見、問題8と似てるようにも思えますが、うまい解法が思いつかなかったのでしらみつぶしで調べることにしました。まずはデータの事前加工。 二次元…

問題10: 200万以下の全ての素数の和を求める[=>問題文] なんだかずいぶん投げやりな問題ですね。問題3で素数リストを作成する「エラトステネスのふるい関数」をつくってあるので活用しましょう。 問題10の解答 (defun problem010 (N) (apply #'+ (cons 0.0 (…

問題9: a+b+c=1000 かつ a^2+b^2=c^2 (a<b<c) を満たす唯一の a b c の積を求めよ。[=>問題文] 問題9の解答 (defun problem009 (N) (let ((a 0) (ans nil)) (while (and (null ans) (< (incf a) N)) (let* ((a2 (* a a)) (n (- N a)) (b (1+ a)) (c 0)) (while (and (null ans) (< b (setq c (- n b)))) (</b<c)>…

問題8: 提示された1000桁の数字列内で連続する5つの数字の積の最大はいくつか。[=>原文和訳] 問題8 解答 ちょっと凝った作りになりました。 (defun problem008 (str) "数字列内の5個の連続する数字の積の最大値を取得" (let ((N 5) (ans 0) (blk nil)) (doli…

問題7: 10001 番目の素数を求めよ。[=>原文和訳] 問題7の解答 (defun problem007 (N) "N番目の素数を取得" (let ((primes-list '(2)) (n 1) (count (1- N))) (while (> count 0) (incf n 2) (let ((p 0)) (dolist (p primes-list) (when (< (floor (sqrt n))…

問題6: 最初の100個の自然数について和の二乗と二乗の和の差を求めよ。[=>原文和訳] 問題6の解答 (require 'cl) (defun problem006 (N) (- (expt (/ (* N (1+ N)) 2) 2) (let ((n 0) (total 0)) (dotimes (n N total) (incf total (expt (1+ n) 2)))))) (pro…

問題4: 3桁の数の積で表される回文数のうち最大のものはいくらになるか。[=>原文和訳] 今回は力技でもすぐ答えが出そうな簡単な問題です。 回文数チェック関数 (defun is-palindromic-number (x) "回文数チェック" (let* ((str (number-to-string x)) (sub-l…

問題5: 1 から 20 までの整数全てで割り切れる数字の中で最小の値はいくらになるか[=>原文和訳] 20の階乗は float型で正確な整数を扱える範囲を超えてしまいます。ですが、今回は階乗ではなく最小公倍数なので floatや、もしかしたら integer の範囲で収まる…

問題3: 600851475143 の素因数のうち最大のものを求める。[=>原文和訳] Emacsのversion 今回は微妙に環境依存の話なので、最初にうちの開発実行環境を書いておきます。 (version) >"GNU Emacs 22.3.1 (i386-msvc-nt5.1.2600) of 2009-08-10 on KOICHIRO-PC" …

400万未満のフィボナッチ数列の項において、偶数値になる項の和を求める。[=>原文和訳] ごく普通に数列を作りながら判定して加算。 (require 'cl) (defun problem002-1 () (let ((N 4000000) (a 1) (b 2) (total 2)) (while (< (setq c (+ a b)) N) (if (eve…

遅ればせながら Project Euler というプログラム問題サイトを知りました。せっかくなので、自分の解答を残していこうと思います。言語は、C/C++ Javascript ひまわり(w) なんかを検討した末、 せっかくなら他の人があまりやっていないものを、そして一度じっ…