Problem 37 - 切り詰め可能な素数

久しぶりに素数問題。

3797は面白い性質を持っている. まずそれ自身が素数であり, 左から右に桁を除いたときに全て素数になっている (3797, 797, 97, 7). 同様に右から左に桁を除いたときも全て素数である (3797, 379, 37, 3).
右から切り詰めても左から切り詰めても素数になるような素数は11個しかない. 総和を求めよ.
注: 2, 3, 5, 7を切り詰め可能な素数とは考えない.

問題の意図を把握してなくて苦労した。

3797, 797, 97, 7の中で、97は右から切り詰めると素数にならない。キャッシュを使って探してたら5つしか見つからなかったり。

はっきりした上限がわからないので、11個見つけたら終わる。という感じにしてみた。

(define (prime? n)
  (letrec ((trial-divisor
             (lambda (t)
               (or (< n (* t t))
                   (and (not (zero? (remainder n t)))
                        (trial-divisor (+ t 2)))))))
    (and (> n 1)
         (or (= n 2)
             (and (odd? n)
                  (trial-divisor 3))))))

(define (problem37 x)
  (letrec ((primers? (lambda (f n)
                       (and (prime? n)
                            (or (zero? (quotient n 10))
                                (primers? f (f n))))))
           (down-split (lambda (n) (quotient n 10)))
           (up-split (lambda (n)
                       (modulo n
                               (expt 10
                                     (inexact->exact
                                       (floor
                                         (/ (log n) (log 10))))))))
           (iter (lambda (n finds acc)
                   (cond ((= finds x) acc)
                         ((and (prime? n)
                               (primers? down-split n)
                               (primers? up-split n))
                          (iter (+ n 2) (+ finds 1) (cons n acc)))
                         (else
                           (iter (+ n 2) finds acc))))))
    (apply + (iter 11 0 '()))))

(problem37 11)
; (739397 3797 3137 797 373 317 313 73 53 37 23)
; 748317

だいぶand,or再帰に慣れてきた。

最後を見つけるまでが重い。左右切り詰めのキャッシュを使って検索すれば、上限もわかるし、かなり早くなりそう(改造する気なし)