ホーム - Project Euler

Problem 27¶

Quadratic Primes¶

Euler discovered the remarkable quadratic formula:

$n^2 + n + 41$

It turns out that the formula will produce $40$ primes for the consecutive integer values $0 \le n \le 39$. However, when $n = 40, 40^2 + 40 + 41 = 40(40 + 1) + 41$ is divisible by $41$, and certainly when $n = 41, 41^2 + 41 + 41$ is clearly divisible by $41$.

The incredible formula $n^2 - 79n + 1601$ was discovered, which produces $80$ primes for the consecutive values $0 \le n \le 79$. The product of the coefficients, $-79$ and $1601$, is $-126479$.
Considering quadratics of the form:

$n^2 + an + b$, where $|a| < 1000$ and $|b| \le 1000$

where $|n|$ is the modulus/absolute value of $n$
e.g. $|11| = 11$ and $|-4| = 4$

Find the product of the coefficients, $a$ and $b$, for the quadratic expression that produces the maximum number of primes for consecutive values of $n$, starting with $n = 0$.

二次式素数¶

オイラーは以下の二次式を考案している:

$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 の連続する整数で80個の素数を生成する. 係数の積は, -79 × 1601 で -126479である.

さて, |a| < 1000, |b| ≤ 1000 として以下の二次式を考える (ここで |a| は絶対値): 例えば |11| = 11 |-4| = 4である.

$n^2 + an + b$

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

(import (scheme base)
        (gauche base)
        (math prime)
        (scheme sort))

(define temp-primes (primes))

(define (prime? n)
  (= n
     (find (^p (<= n p))
           temp-primes)))

(define (consecutive-prime a b)
  (let loop ([n 0])
    (if (prime? (+ (expt n 2)
                   (* n a)
                   b))
      (loop (+ n 1))
      n)))

(define ab-combinations
  (fold-right
    (^[m result]
      (append
        (fold-right
          (^[n result]
            (cons `(,m . ,n) result))
          '()
          (iota (+ 1 (* 1000 2)) -1000))
        result))
    '()
    (iota (+ 1 (* 999 2)) -999)))

;; これでいけると思ったけどうまくいかなかった…
;; 何か見落としてるっぽい…
;(define ab-combinations
;  (fold-right
;    (^[m result]
;      (append
;        (fold-right
;          (^[n result]
;            (cons `(,m . ,n) result))
;          '()
;          (iota (+ (div (- -1 m)
;                        2)
;                   1)
;                3
;                2))
;        result))
;    '()
;    (iota 499 -997 2)))

(define consecutive-list
  (map
    (^c
      (cons* (car c)
             (cdr c)
             (consecutive-prime (car c) (cdr c))))
    ab-combinations))

(define answer-27
  (let ([answer-abc (car (list-sort
                           (^[a b]
                             (> (cddr a) (cddr b)))
                           consecutive-list))])
    (* (car answer-abc) (cadr answer-abc))))

(format #t "27: ~d~%" answer-27)