素数のお勉強 2 - 完全数

Scheme

Problem 23 - PukiWikiがよくわからないので、ちょっと勉強中。


2進数で表すと、1111...1と並んでいる数の事をメルセンヌ数という。M_p=2^p - 1の形で表せる。

メルセンヌ数のなかで、素数となるものをメルセンヌ素数という。pが素数であるとき、メルセンヌ素数が現れる。

ふむふむ。


とりあえず20までの素数を出す。

(filter prime? (iota (- 20 1) 2)) ; (2 3 5 7 11 13 17 19)

2^p - 1する

(map (lambda (n)
       (- (expt 2 n) 1))
     (filter prime? (iota (- 20 1) 2))) ; (3 7 31 127 2047 8191 131071 524287)

素数かどうかフィルタリング。

(filter prime?
        (map (lambda (n)
               (- (expt 2 n) 1))
             (filter prime? (iota (- 20 1) 2)))) ; (3 7 31 127 8191 131071 524287)

メルセンヌ素数が出た。M_11は素数ではないらしい。

あんまり大きな数でやると素数フィルタリングが終わらない。注意。


その数自身を除く約数の和がもとの数に戻る数の事を完全数という。6 = 1 + 2 + 3とか。

完全数とメルセンヌ素数の関係は深く、メルセンヌ素数から完全数を導き出せるらしい。やってみる。

メルセンヌ素数から、完全数を出すには、M_n * (M_n + 1) / 2

(map (lambda (n)
       (* n (+ n 1) 1/2))
     (filter prime?
             (map (lambda (n)
                    (- (expt 2 n) 1))
                  (filter prime? (iota (- 20 1) 2)))))
; (6 28 496 8128 33550336 8589869056 137438691328)

おぉ。完全数が出てきた。


とりあえず1行目を理解した。

参考