Problem 58 - 対角線の中に現れる素数

50問を目前に解ける問題が少なくなってきた。全然解けそうな感じの問題が無い。

Problem 58 - PukiWiki

1から初めて, 以下のように反時計回りに数字を並べていくと, 辺の長さが7の渦巻きが形成される.

(図)

面白いことに, 奇平方数が右下の対角線上に出現する. もっと面白いことには, 対角線上の13個の数字のうち, 8個が素数である. ここで割合は8/13 ≈ 62%である.

渦巻きに新しい層を付け加えよう. すると辺の長さが9の渦巻きが出来る. 以下, この操作を繰り返していく. 対角線上の素数の割合が10%未満に落ちる最初の辺の長さを求めよ.

凄く興味深い。

確か前にも対角線の問題があったので参考にしてみた。

(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 (problem58 x)
  (letrec ((primers-filter (lambda (n)
                             (filter prime?
                                     (map (lambda (x)
                                            (- (* n n) (* x (- n 1))))
                                          '(1 2 3)))))
           (iter (lambda (n acc)
                   (let* ((res (append (primers-filter n) acc))
                          (len (length res))
                          (p (/ len (+ (* (quotient n 2) 4) 1))))
                     (if (< p x)
                         n
                         (iter (+ n 2) res))))))
    (iter 3 '())))

(problem58 0.2) ; 309
(problem58 0.1) ; 26241

そろそろ試し割り素数判定はやばくなってきた。

10%への道が長すぎだよ。