読者です 読者をやめる 読者になる 読者になる

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)))))

sbcl

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

xyzzy

(time (test 2000000))
7719 msec
8429539

sieveは与えられた数値以下の素数のリストを返す関数。中身はこれxyzzyだと(sieve 10000000)は1分以上かかる。

O'REILLYの新刊に素数の本があったから見てみようかな。

プライムナンバーズ ―魅惑的で楽しい素数の事典 (O’Reilly math series)

プライムナンバーズ ―魅惑的で楽しい素数の事典 (O’Reilly math series)