problem 97 - mtsuyuguの日記

一気に飛んで problem 97。2,357,207 桁からなるメルセンヌ数でない素数 28433*2^7830457+1 の下 10 桁を求める問題。

(expt 2 7839457) とするのではなくて、10桁を超えないように常に下10桁に対して 2 を掛けるようにはしているものの、根性型のプログラミングであることに異論を挟むつもりはございません。

(define (expt2-last10 n)
  (let loop ((i 0)
             (result 1))
    (if (>= i n)
      result
      (loop (+ i 1) (modulo (* 2 result) 10000000000)))))

(define (p97)
  (modulo (+ (* 28433 (expt2-last10 7830457)) 1) 10000000000))

(print (p97))

ちなみに

$2^n \geq 10^{10}$
$n\log_{10}2 \geq 10$
$n \geq \frac{10}{\log_{10}2}$
$n \geq \frac{10\log10}{\log2} = 33.219280948873624...$

なので 2^x が初めて 10 桁を超えるのは 2^34。