Google Treasure Hunt
Google Treasure Hunt 2008
Official Google Blog: Google Treasure Hunt update
こんなん見つけたんだけど流行ってなさそう。現在4問公開中。
過去問3問は目で解けたり*scratch*で解ける程度の難易度なんだけど、素数の問題はちょっと重い。
#| Google Treasure Hunt 2008 Question: Find the smallest number that can be expressed as the sum of 5 consecutive prime numbers, the sum of 11 consecutive prime numbers, the sum of 775 consecutive prime numbers, the sum of 1151 consecutive prime numbers, and is itself a prime number. For example, 41 is the smallest prime number that can be expressed as the sum of 3 consecutive primes (11 + 13 + 17 = 41) and the sum of 6 consecutive primes (2 + 3 + 5 + 7 + 11 + 13 = 41). |# #+xyzzy(require "euler/util") #-xyzzy(load "../euler/util.fasl") (defparameter q '(5 11 775 1151)) (defun sums (l n) (loop for s = (loop for i from 0 to (1- n) sum (nth i l)) then (+ succ (- s head)) for succ in (nthcdr n l) for head in l collect s)) (defun myintersection (l1 l2) (let (result a b) (while (and l1 l2) (setq a (car l1) b (car l2)) (cond ((= a b) (setq result (nconc result `(,a)) l1 (cdr l1) l2 (cdr l2))) ((< a b) (setq l1 (cdr l1))) (t (setq l2 (cdr l2))))) result)) (defun test (n) (let ((primes (sieve n))) (find-if #'primep (reduce #'myintersection (mapcar #'(lambda (sums primes a)) q)))))
CL-USER> (time (test 1000000)) Evaluation took: 0.188 seconds of real time 0.187500 seconds of total run time (0.156250 user, 0.031250 system) [ Run times consist of 0.031 seconds GC time, and 0.157 seconds non-GC time. ] 100.00% CPU 544,821,457 processor cycles 10,694,408 bytes consed NIL CL-USER> (time (test 10000000)) Evaluation took: 5.328 seconds of real time 5.328125 seconds of total run time (2.140625 user, 3.187500 system) [ Run times consist of 3.641 seconds GC time, and 1.688 seconds non-GC time. ] 100.00% CPU 9,945,873,434 processor cycles 131,145,920 bytes consed 8429539
(time (test 2000000)) 7719 msec 8429539
sieveは与えられた数値以下の素数のリストを返す関数。中身はこれ。xyzzyだと(sieve 10000000)は1分以上かかる。
O'REILLYの新刊に素数の本があったから見てみようかな。
プライムナンバーズ ―魅惑的で楽しい素数の事典 (O’Reilly math series)
- 作者: David Wells,伊知地宏(監訳),さかいなおみ
- 出版社/メーカー: オライリージャパン
- 発売日: 2008/10/25
- メディア: 単行本
- クリック: 15回
- この商品を含むブログ (34件) を見る