Problem 27 - 素数生成式

Scheme

素数な問題。

Problem 27

オイラーは以下の二次式を考案している:
n^2 + n + 41.

この式は, nを0から39までの連続する整数としたときに40個の素数を生成する. しかし, n = 40のとき40^2 + 40 + 41 = 40(40 + 1) + 41となり41で割り切れる. また, n = 41のときは41^2 + 41 + 41であり明らかに41で割り切れる.

計算機を用いて, 二次式 n^2 - 79n + 1601という式が発見できた. これはn = 0 から 79 の連続する整数で素数を生成する. 係数の積は, -79 × 1601 で -126479である.

さて, |a| < 1000, |b| < 1000 として以下の二次式を考える (ここで|a|は絶対値):
n^2 + an + b

n=0から初めて連続する整数で素数を生成したときに最長の長さとなる上の二次式の, 係数a, bの積を答えよ.

定義どおりに書けばいいんだけど、2000*2000回計算しなければならないので、かなりステップ数が多くなる。

素数になる条件を絞り込めば早くなりそうなんだけど、とりあえず全部試してみる。

(define (problem27 n)
  (letrec ((make-primers (lambda (n a b)
                           (let ((p (+ (* n n) (* a n) b)))
                                (if (or (negative? p) (not (prime? p)))
                                    '()
                                    (cons p
                                          (make-primers (+ n 1) a b))))))
           (iter (lambda (m a b)
                   (cond ((>= a n) m)
                         ((>= b n) (iter m (+ a 1) (- n)))
                         (else
                           (let* ((p (make-primers 0 a b))
                                  (len (length p)))
                                 (iter
                                   (if (> len (car m))
                                       (list len a b p)
                                       m)
                                   a (+ b 1))))))))
          (iter (list 0 0 0 '()) (- n) (- n))))

(problem27 1000)
; (71 -61 971
;(971 911 853 797 743 691 641 593 547 503 461 421 383 347 313 281 251 223 ...

(* -61 971) ; -59231

素数判定部分は略。

n^2 - 61n + 971で71個素数を生成できる式を見つけ出すことが出来た。

  • どのような条件で素数が生成されるのか考えれば高速化できるはず。
    • nが0の時、素数が生成出来なければいけないので、bは正で必ず素数だ。倍以上早くなる。
    • aの条件は何だろう・・・むぅぅ。考えてみる。
  • 1000より少ない正の整数でa,bを絞ると、a=1,b=41が最大になった。
  • an^2 + bn + cで見つける方法もあるらしい。