Problem 46 - 奇合成数

Scheme

オイラーと同時代の数学者Christian Goldbachに関する問題。


Problem 46 - PukiWiki

奇合成数25は、25 = 7 + 2 * 3^2のように、素数 + 2 * 平方数で表せる。という予想を打ち破れ。という問題。

ゴールドバッハの予想 - Wikipediaとはちょっと違うみたい。


まず、奇合成数の判定。

奇合成数は9,15,21,25,...素因数分解すると、{3,3}, {3,5}, {3,7}, {5,5}...

素因数分解して全て奇数か？なんてやってると大変そうなので、奇数で、素数ではなければ、奇合成数であるとしとこう


25を1から順に二倍の平方数で引いてやると、

25 - 2 * 1^2 = 23

となり、

25 = 7 + 2 * 3^2

にならないので、平方は大きいほうからテストしていくことにする。


微妙に迷走しながら仕上げた。

(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 (problem46)
  (letrec ((test
             (lambda (n k)
               (let ((p (- n (* 2 (* k k)))))
                 (and (not (zero? k))
                      (or (prime? p)
                          (test n (- k 1)))))))
           (iter
             (lambda (n)
               (if (not (or (prime? n)
                            (test n (inexact->exact (floor (sqrt (/ n 2)))))))
                     n
                     (iter (+ n 2))))))
    (iter 3)))

(problem46) ; 5777


はいっと。