Project Euler Problem 29

問題29: 2<=a<=100, 2<=b<=100 において、a^b で作成される数は重複を除いて何個あるか[=>問題文]

問題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-bigint a))
            (acc (integer-to-bigint a)))
        (do ((b 2 (1+ b)))
            ((> b limit))
          (setq acc (bigint* acc n))
          (push acc lis)))))))

(problem029a 100)

　特別なことはしていません。作成される数をリストにすべて保存し、delete-dups で重複を除去しています。100の100乗は明らかに多倍長数なので、bigintライブラリを使っています。
　bigintライブラリに新たに integer-to-bigint を追加しました。整数からbigintへ文字列を経由することなくダイレクトに変換できるようになりました。また掛け算関数 bigint* にバグがあったので修正しました。
　ところで、delete-dups は遅いらしいです。対象データが多いときは hash-table を使ったほうが良いらしい。というわけで。

問題29の解答その２ (hash-table + hash-table-count)

(defun problem029b (limit)
  (hash-table-count
   (do ((a 2 (1+ a)) (ht (make-hash-table :test #'equal)))
       ((> a limit) ht)
     (let ((n (integer-to-bigint a))
           (acc (integer-to-bigint a)))
       (do ((b 2 (1+ b)))
           ((> b limit))
         (setq acc (bigint* acc n))
         (puthash acc t ht))))))

(problem029b 100)

　hash-table はデフォルトではキーの比較に eq を使いますが、今回はbigint、つまりリストをキーにするので equal で比較するよう、make-hash-table に指定しています。ちなみに、delete-dups は equal 比較で固定されています。

どれくらい違うか

Function     Avg (sec)
===========  ========= 
problem029a  1.615900  delete-dups 版
problem029b  0.196600  hash-table 版

　これはまた、想像以上に差がつきました。

問題29の解答その３

　実際に指数計算しなくても、素因数分解結果を保持していれば生成される数のパターンは数えられることに気づきました。これならば多倍長演算不要です。

(require 'cl)
(require 'math-lib) ;factorize

(defun problem029c (limit)
  (let* ((primes (primes-sieve (truncate (sqrt limit))))
	 (parse
	  (lambda (a b)
	    (mapcar #'(lambda (pair)
			(cons (car pair) (* b (cdr pair))))
		    (factorize a primes)))))
    (hash-table-count
     (do ((a 2 (1+ a)) (ht (make-hash-table :test #'equal)))
	 ((> a limit) ht)
       (do ((b 2 (1+ b)))
	   ((> b limit))
	 (puthash (funcall parse a b) t ht))))))

(problem029c 100)

　parse にて (a b) の組から a^b の計算結果を素因数分解したリストを作成します。factorize は素因数分解の結果を 素因数の小さいほうから並べたリストで返しますので sort 不要です。（順序が保証されなければここで sort が必要になります。