問題31: イギリス硬貨 1ペンス〜2ポンドを使い 2ポンドをつくる方法は何通りあるか。[=>問題文] 問題31の解答 ;; Emacs lisp (require 'cl) (defun problem031a (n) (labels ((repeat (coins acc) (if (null coins) 0 (do ((add (car coins)) (next-coins (c…

問題30: 2以上の自然数について、各桁を5乗した数の和が元の数と一致する数をすべて求め、その和を答えよ。[=>問題文] 上限が与えられない問題です。左辺の値いくつまで調べればよいのか。注目するのは「桁数」です。 k 桁の数を考えます。各桁の最大値は 9 …

問題29: 2[=>問題文] 問題29の解答 (list + delete-dups) ;; Emacs Lisp (require 'cl) (require 'bigint) ;integer-to-bigint, bigint* (defun problem029a (limit) (length (delete-dups (do ((a 2 (1+ a)) (lis)) ((> a limit) lis) (let ((n (integer-to…

問題28:渦巻状に自然数を並べた1001x1001数方陣の対角線上にある数の合計を求める。方陣の詳細はリンク先参照[=>問題文] 問題28の解答 ;; Emacs Lisp (require 'cl) (defun problem028 (N) (do ((n 3.0 (+ n 2)) (result 1)) ((> n N) result) (let ((d (1- …

問題27: 二次式 n^2 + an + n = p (|a| 素数) において、n に 0から連続する整数を代入したときもっとも大きな n まで式が成り立つ a b の組を求め、その積を答えよ。[=>問題文] 効率的な素数判定方法を考えていたら2日経ってしまいました。最終的に、処理時…

問題26: 1000未満のdにおいて 1/d を小数にした時、循環部の長さがもっとも長くなる d を求めよ。[=>問題文] 問題26の解答 気がつけば do ばっかり使ってる自分がいる。 ;; Emacs Lisp (defun problem026 (limit) (let ((recurring-length ; 1/d の循環部の…

問題25: フィボナッチ数列の項 F(n) が千桁になる最初の n を求めよ。ただし F(1)=F(2)=1とする。[=>問題文] 問題25の解答 bigint ライブラリの出番です。 ;; Emacs Lisp (require 'bigint) (defun problem025 (digit) (do ((fn (string-to-bigint "0")) (fn…

問題24: 0〜9の10個の数字で辞書順に順列を作る。100万番目のパターンは何か[=>問題文] 順列生成ロジックはライブラリに入れたいですね。さてどう作ろう。 順列生成というと、私の場合再帰関数で作るのが一番最初に思い浮かびます。でも再帰で順列を作ると再…

問題23: 2つの過剰数の和で書き表せない正の整数の総和を求めよ.(28123より大きい整数は2つの過剰数の和で表せることがわかっている）。[=>問題文] だんだん手ごたえのある問題になってきましたね。 問題23の解答 math-lib はこちら。 ;; Emacs Lisp (requir…

問題22: ファイルに保存されている全ての名前のスコアを計算しその合計を求めよ。[=>問題文] 問題22の解答 ;; Emacs Lisp (require 'cl) (defun problem022 (file-path) (labels ((read-names () ;; ファイルから名前リスト読み込み (let ((tmp) (buffer (fi…

;; ;; math-lib.el ;; 利用するときは、このファイルをload-pathの通ったところに置いて ;; バイトコンパイルして、require してください。 (provide 'math-lib) (require 'cl) (defun primes-sieve (n) "エラトステネスのふるい (n未満の素数を列挙)" (let*…

問題21: 10000未満の友愛数の合計を求めよ。[=>問題文] 素数リスト、素因数分解、約数、メモ化と、これまでに出てきた要素がいろいろ活用できる良い問題ですね。 問題21の解答 ;; Emacs Lisp (require 'cl) (require 'math-lib) (defun problem021 (n) (let …

今後も使うかもしれないのでここにまとめておきます。 加算、乗算、累乗、階乗が実装済みです。 多倍長演算ライブラリ ;; ;; bigint.el ;; 利用するときは、このファイルをload-pathの通ったところに置いて ;; バイトコンパイルして、require してください。…

問題20: 100! の各桁の数字の合計を求めよ。[=>問題文] 問題20の解答 ;; Emacs Lisp (require 'cl) (require 'bigint) (defun problem020 () (let ((str (bigint-to-string (bigint-fact 100)))) (apply #'+ (mapcar #'(lambda (c) (- c ?0)) str)))) (probl…

問題19: 1900/1/1は月曜日である。では20世紀で月の初めが日曜日になるのは何回あるか。[=>問題文] 問題19の解答 ;; Emacs Lisp (defun problem019 () (let* ((table [31 31 28 31 30 31 30 31 31 30 31 30]) (day (- (1+ 365) (aref table 0))) (count 0)) …

問題18: 数字で構成される三角形を頂点から最下段まで移動する。経路の合計がもっとも大きくなる時の値を求めよ。[=>問題文] 問題18の解答 「経路の総当りをする」という発想がむしろ出ませんでした。 ;; Emacs Lisp (require 'cl) (defun problem018 (data)…

問題17: 1 から 1000 までの数字をすべて英単語で書くと全部で何文字になるか。[=>問題文] 問題17の解答 数詞の法則が奇妙な国って意外に多いです。ゼロの発明以前から人類が「数」を使っていた証でしょうか。 ;; Emacs Lisp (require 'cl) (defun problem01…

問題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 の範囲で収まる…