Problem 49 - 等差数列に潜む素数

Scheme

等差数列と素数の関係に関する問題。


Problem 49 - PukiWiki

項差3330の等差数列1487, 4817, 8147は次の2つの変わった性質を持つ。

  • 3つの項はそれぞれ素数である。
  • 各桁は他の項の置換で表される。

もう一個4桁の中に同じ性質を持つものがあるらしい。


作戦としては、

  • 4桁の素数を全部出す。
  • 素数リストから2つの数をピックアップして比較していく。
  • 2番目の素数は素数であることが明らかなので、2番目の数が置換できるかどうかチェック。
  • 等差数列なので、差を取って3番目を出して、置換チェック、素数チェックを行う。

という感じ。


(problem49 3)と最初の数がズレている事に気づかず、5桁を求めてた。5桁は泣けるよ。

(define (prime? n)
  (letrec ((e (sqrt n))
           (trial-divisor
             (lambda (t)
               (or (> t e)
                   (and (not (or (zero? (modulo n t))
                                 (zero? (modulo n (+ t 2)))))
                        (trial-divisor (+ t 6)))))))
    (and (> n 1)
         (or (<= n 3)
             (and (odd? n)
                  (not (zero? (modulo n 3)))
                  (trial-divisor 5))))))

(define (number->list n . base)
  (letrec ((b (if (null? base) 10 (car base)))
           (iter (lambda (acc n)
                   (let ((q (quotient n b))
                         (m (cons (modulo n b) acc)))
                        (if (zero? q)
                            m
                            (iter m q))))))
    (iter '() n)))

(define (problem49 k)
  (letrec ((iter
             (lambda (ps)
               (if (null? ps)
                   '()
                   (let* ((p (car ps))
                          (pl (sort (number->list p) <))
                          (res (filter (lambda (x)
                                         (let ((next (+ x (- x p))))
                                           (and (< next (expt 10 (+ k 1)))
                                                (equal? (sort (number->list x) <) pl)
                                                (equal? (sort (number->list next) <) pl)
                                                (prime? next))))
                                       (cdr ps))))
                     (if (not (null? res))
                         (cons (list p (car res)) (iter (cdr ps)))
                         (iter (cdr ps))))))))
    (map (lambda (l)
           (list (car l)
                 (cadr l)
                 (+ (cadr l) (- (cadr l) (car l)))))
         (iter (filter prime? (iota (- (expt 10 (+ k 1)) (expt 10 k))
                                    (expt 10 k)))))))

(problem49 3) ; ((1487 4817 8147) (2969 6299 9629))
(problem49 4) ; ((11483 14813 18143) (11497 41719 71941) ...

5桁はいっぱいあるよｗ

問題をよく読もう。