Project Euler 134，約10分。

Lisp

どもです。
だんだんとクロールが下手になっていっている気がしないでもないです。
そうそう，相方さん家にて，バジルとシソを蒔きました。
だめもとで。出たらラッキー。
シソの種のパッケージに，一昼夜水に浸けておけと書いてあったので，
その通りにしましたよ。
培地はというと，もち，新プランター栽培用の培地。
相方さん家にプラポットのチマサンチュ2つが行っているので，
それを撤収して，培地を洗って再利用。
100均で土入れっていうの? 筒状になっているやつを買ってもらったのですが，
それがすこぶる役に立ってくれた。今まで匙とかでやっていたせいもあるが，
何しろ，培地がこぼれない。んで，けつの方で，培地を押してギュッギュッって
できる。すげーぜ。
しかもなんと，それともっとでかいスコップ的なのがセットになって
いるんです! でっかいプランターとかに培地を入れる場合はこちらを，
ほいで，ちっさいポットとかに入れるには筒状のやつを。
という感じで，フルティカとかスタピストマトとかの種蒔きを
先延ばしにしていることをごまかせますでしょうかね。

522.406 seconds

おそっ。
1回目に提出したときは，p2 <= (expt 10 6) という条件を勝手に
盛り込んでしまっていて不正解。

CL-USER> (time (euler-problem-134 (expt 10 6)))
Invoking restart: Continue from break.
(EULER-PROBLEM-134 (EXPT 10 6)) took 522,406 milliseconds (522.406 seconds) to run 
                    with 4 available CPU cores.
During that period, 507,031 milliseconds (507.031 seconds) were spent in user mode
                    0 milliseconds (0.000 seconds) were spent in system mode
31 milliseconds (0.031 seconds) was spent in GC.
 14,800,736 bytes of memory allocated.

(defun find-e134-number (p1 p2)
  (loop with base = (expt 10 (1+ (floor (log p1 10))))
        with step = (mod base p2)
        for n from 1
        for residual = step then (mod (+ residual step) p2)
        with diff = (- p2 p1)
        when (= diff residual)
          return (+ p1 (* base n))))

(defun euler-problem-134 (upper-bound)
  (loop with primes = (coerce (cddr (primes (+ 100 upper-bound))) 'vector)
        for i from 0 below (1- (length primes))
        while (< (svref primes i) upper-bound)
        summing (find-e134-number (svref primes i) (svref primes (1+ i)))))


さて，1分以内を目指すためにググったりフォーラムに行ってきまうー。

追記 (2012/03/27 (Tue) 19:21)

よっしゃ。1分以内。

CL-USER> (time (euler-problem-134-2 (expt 10 6)))
(EULER-PROBLEM-134-2 (EXPT 10 6)) took 3,875 milliseconds (3.875 seconds) to run 
                    with 4 available CPU cores.
During that period, 3,813 milliseconds (3.813 seconds) were spent in user mode
                    16 milliseconds (0.016 seconds) were spent in system mode
78 milliseconds (0.078 seconds) was spent in GC.
 22,441,080 bytes of memory allocated.


参考ページ


拡張ユークリッド互除法を使うと，剰余における逆元を求められると。
なるほど。ちょっと感動した。

(defun extgcd (a b)
  ;;(declare (optimize (debug 3)))
  (if (zerop b)
      (cons 1 0)
      (let ((prev (extgcd b (mod a b))))
        (cons (cdr prev)
              (- (car prev) (* (cdr prev)
                               (truncate a b)))))))

;; ax ≡ b (mod modulus) を満たす x を1つ求める。
(defun inverse-mod (a b modulus)
  (when (= 1 (gcd a modulus))
    (let ((cell (extgcd a modulus)))
      (mod (* (car cell) b) modulus))))

(defun euler-problem-134-2 (upper-bound)
  (loop with primes = (coerce (cddr (primes (+ 100 upper-bound))) 'vector)
        for i from 0 below (1- (length primes))
        for p1 = (svref primes i)
        for p2 = (svref primes (1+ i))
        while (< p1 upper-bound)
        summing (* p2 (inverse-mod p2 p1 (expt 10 (1+ (floor (log p1 10))))))))