戻る



ーーーーーーＲａｃｋｅｔの素数生成プログラムーーーーーー
Ｒａｃｋｅｔの素数の生成プログラムは、Ｒａｃｋｅｔの数の理論のライブラリに、
素数判定の関数が用意されているためある意味簡単です。
（それにたどり着くまでに時間がかかりましたが。）
Ｒａｃｋｅｔドキュメンテーションにより次のコードが見つかりました。

(require math/number-theory)
(filter prime? (range 1 100 1))

実行結果は次のようになります。

(list 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97)

１００までの素数ならすぐに実行してもらえますが、１００万までの素数を実行させると、
メモリが足りませんと実行できませんでした。
ネットで検索すると素数については、たくさんの研究・資料がありました。
「エラトステネスのふるい」の方法などを使ったコードもありますが、
私には少しむずかしく感じられました。
ーーーーーーエラトステネスのふるいーーーーーー
エラトステネスのふるいのＲａｃｋｅｔのシンプルなプログラムを
見つけましたので紹介します。
参考にしたのは以下のサイトです。
http://yoshiiz.blog129.fc2.com/blog-entry-391.htm
コードは次のようになります。



(require (lib "1.ss" "srfi"))

(define notMultiple?

　(lambda (p)

　　(lambda (x) (not (zero? (modulo x p))))))


(define sieve

　(lambda (ls)

　　(if (null? ls)

　　　 '() 

　　   (cons (car ls) (filter (notMultiple? (car ls))

　　　　　　　　　 　　　　      (sieve (cdr ls)))))))


(define (eratosthenes n)

　　(display  (sieve (iota (- n 1) 2 1))))

以上を実行してから
(eratosthenes 100)　を実行すると

(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97)

１００までの素数のリストが求まります。
（注） sieve は　ふるい　の意味です。
n を　たとえば　１００　とすると
(iota 99 2 1)は
(2 3 4 5 6 ～　98 99)　　になります。
(iota 項数　初項　等差)です。
(sieve (iota 99 2 1)) で１００までの素数リストができます。
最初に　２の倍数を消して、次に３の倍数を消してとやっていくのですが、
５０以上はやる必要がありませんので、
このプログラムは効率が悪いのですが、シンプルでなんとなく分かるコードで好きです。
（もっと効率を求めると　ルート１００以上はチェックする必要がありません。
　そういったテクニックをやらない分、紹介したコードはシンプルなのだと思います。）
　 ーーーーーー完全数その１ーーーーーー
完全数について（及び完全数を作成するために使うメルセンヌ素数について）
Ｒａｃｋｅｔを使ってあれこれ試してみました。
参考サイトは以下です。
http://d.hatena.ne.jp/tanakaBox/20080409/1207743974
完全数は以下のリストです。

(list 6 28 496 8128 33550336 8589869056 137438691328)
例えば　第１項の６の場合は、約数が１、２，３なので全部足すと６です。（１も入れます）
6 は完全数です。
例えば　第２項の２８の場合は、約数が　１、２，４，７，１４なので全部足すと２８になります。
28 は完全数です。 約数をリストとしてあげる関数divisorsがＲａｃｋｅｔに用意されています。
例えば　４９６の場合にＲａｃｋｅｔを使って約数をリストアップするには

(divisors 496)
を実行すると

(list 1 2 4 8 16 31 62 124 248 496)
となります。
divisors は　１とその数自身もリストアップされます。
(sum 0 (divisors 496))
とリストアップされた約数を全部足すと992 となります。
（496自身も足していますので992から496を引くと496になります。
496 も完全数でした。

次の ８１２８　もやってみます。
(divisors 8128)
(list 1 2 4 8 16 32 64 127 254 508 1016 2032 4064 8128)
> (sum 0 (divisors 8128))
16256
８１２８も完全数です。

（コードは以下のとおりです。)

(require (lib "1.ss" "srfi"))  

(require math/number-theory)


(filter prime? (iota (- 20 1) 2))

　　→→(list 2 3 5 7 11 13 17 19)


(map (lambda (n)

       (- (expt 2 n) 1))

     (filter prime? (iota (- 20 1) 2)))

　　　→→(list 3 7 31 127 2047 8191 131071 524287)

(list 3 7 31 127 2047 8191 --)　をメルセンヌ数といいます。
この中で素数の場合はメルセンヌ素数といいます。
メルセンヌ数の　２０４７　は素数ではありません。

(divisors 2047)
(list 1 23 89 2047)
となり２０４７＝２３×８９

(map (lambda (n)

       (* n (+ n 1) 1/2))

     (filter prime?

             (map (lambda (n)

                    (- (expt 2 n) 1))

                  (filter prime? (iota (- 20 1) 2)))))

上記の(filter prime? (map (lambda (n) (- (expt 2 n) 1)(filter prime? (iota 略))))) は
(list 3 7 31 127 8191 131071 524287)になります。
（メルセンヌ素数）

余談ですが、 ｎがメルセンヌ素数のとき（ｎ＝２＾ｐ－１）
（ｎ　＋　１）×　ｎ/2＝2^(p-1) *(2^p -1)
は完全数であることが証明されます。（ユークリッド）
　
（注）(sum 0 ls)は以下のコードです。
(define sum

  (lambda (a ls)

    (cond

      ((null? ls) a)

      (else (sum (+ (car ls) a) (cdr ls))))))
ーーーーーーメルセンヌ素数ーーーーーー
メルセンヌ素数のリストをつくります。


(require (lib "1.ss" "srfi"))
  
(require math/number-theory)


(define (M_n p)

  (- (expt 2 p) 1))


(define (prime-list n)

  (filter prime? (iota (- n 1) 2)))


(define (fact-mer n)

 (for ([i (prime-list n)])

  (cond

    [(prime? (M_n i))

    (display (list i (M_n i)))])))

(prime-list 200)
で２から200までの素数のリストをつくります。
そして、素数ｐから　２のｐ乗マイナス１でメルセンヌ数をつくります。
それから、そのつくったメルセンヌ数の中から素数のものをリストアップします。
(fact-mer 200)
を実行すると次の結果が得られます。

(2 3)
(3 7)
(5 31)
(7 127)
(13 8191)
(17 131071)
(19 524287)
(31 2147483647)
(61 2305843009213693951)
(89 618970019642690137449562111)
(107 162259276829213363391578010288127) (127 170141183460469231731687303715884105727)

ーーーーーー完全数（その２）－－－－－－
前回、メルセンヌ素数から完全数を作る方法で、完全数をリストアップしたが、
メルセンヌ素数とは関係なく完全数を見つける愚直な方法でプログラムを作ってみました。
（サイトで完全数を検索すると、メルセンヌ素数と関係ない完全数はないらしいです。）


(require (lib "1.ss" "srfi"))
  
(require math/number-theory)


(define (comp n)

 (for ([i n])

  (cond

    [(zero? (- (* 2 i) (sum 0 (divisors i))))

     (display i)

     (display "\n")])))


(define sum

  (lambda (a ls)

    (cond

      ((null? ls) a)

      (else (sum (+ (car ls) a) (cdr ls))))))

以上を実行してから　(comp 100000) を実行すると
> (comp 100000)
0
6
28
496
8128
メルセンヌ素数から完全数を作った場合は
メルセンヌ素数　→→　(list 3 7 31 127 8191 131071 524287)
対応する完全数　→→　(list 6 28 496 8128 33550336 8589869056 137438691328)
でしたので、８１２８の次は３３５５０３３６ですので、
(comp 100000000)を実行すればよいのですが、数が大きすぎて実行してもらえません。
ーーーーーー双子素数ーーーーーー
双子素数とは（５７）とか（１１　１３）などのように差が２であるような素数のペアのことです。
プログラムは簡単なので、実行結果を示します。


(require (lib "1.ss" "srfi"))  

(require math/number-theory)


(define (prime-list n)

  (filter prime? (iota (- n 1) 2)))


(define (twin-fact n)

 (for ([i (prime-list n)])

  (cond

    [(prime? (+ i 2))

    (display (list i (next-prime i))) 

    (display "\n")])))

実行すると次の結果が得られます。
(twin-fact 100)
(3 5)
(5 7)
(11 13)
(17 19)
(29 31)
(41 43)
(59 61)
(71 73)
ーーーーーー三つ子素数ーーーーーー
三つ子素数とは（５　７　１１）とか（７　１１　１３）などの隣り合う素数の差が２か４である
３つの素数の組み合わせです。
定式化すると、ｐを素数とすると
（ｐ　ｐ＋２　ｐ＋６）か（ｐ　ｐ＋４　ｐ＋６）のいずれかの形で、３つの素数の組み合わせです。
ｒａｃｋｅｔのプログラムは以下になります。


(require (lib "1.ss" "srfi"))
  
(require math/number-theory)


(define (prime-list n)

  (filter prime? (iota (- n 1) 2)))


(define (tri-fact n)

 (for ([i (prime-list n)])

  (cond

    [(and (prime? (+ i 2))(prime? (+ i 6)))

     (display (list i (+ i 2)(+ i 6)))]

    [(and (prime? (+ i 4))(prime? (+ i 6)))

     (display (list i (+ i 4)(+ i 6)))]

    [else (display "")])))

以上を実行してから

(tri-fact 100)

を実行すると次のようになります。
(tri-fact 100)
(5 7 11)
(7 11 13)
(11 13 17)
(13 17 19)
(17 19 23)
(37 41 43)
(41 43 47)
(67 71 73)
(97 101 103)
ーーーーーーフェルマー素数ーーーーーー
メルセンヌ素数と似ていますが、フェルマー素数を取り上げます。
メルセンヌ素数は、次のようになります。
M_n (P) = 2^p - 1 の形で　ｐは素数で　M_n (p)　も素数の場合です。
フェルマー素数は、次のようになります。
F_n (n) = 2^(2^n) + 1 の形で　F_n (n)　が素数のものです。
Ｒａｃｋｅｔのプログラムは次のようになります。


(require (lib "1.ss" "srfi")) 
 
(require math/number-theory)


(define (F_n n)

  (+ (expt 2 (expt 2 n)) 1))


(define (fact-fer n)

 (for ([i n])

  (display (list i (F_n i) (prime? (F_n i))))

  (display "\n")))

以上を実行してから
(fact-fer 10)を実行します。
> (fact-fer 10)
(0 3 #t)
(1 5 #t)
(2 17 #t)
(3 257 #t)
(4 65537 #t)
(5 4294967297 #f)
(6 18446744073709551617 #f)
(7 340282366920938463463374607431768211457 #f)
(8 115792089237316195423570985008687907853269984665640564039457584007913129639937 #f)
(9 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084097 #f)
> 最初の５項のみ　３　５　１７　２５７　６５５３７　のみフェルマー素数で　#t　が表示されます。
n が５　の時の　4294967297 は素数ではなくて　#f　が表示されます。
(divisors 4294967297)
'(1 641 6700417 4294967297)
となり、641　×　6700417
と素因数分解されます。
ーーーーーー　セクシー素数　－－－－－－
セクシー素数は差が６であるような素数のペアです。
Ｒａｃｋｅｔのプログラムは以下のようになります。
（今までのコードとは少し違った書き方でシンプルにしました。）



(require math/number-theory)

      
(define (sexy-fact n)

 (for ([i n])

  (cond

    [(and (prime?  i)(prime? (+ i 6)))

     (display (list i (+ i 6)))]

    [else (display "")])))

以上を実行してから(sexy-fact 100)　を実行します。
> (sexy-fact 100)
(5 11)
(7 13)
(11 17)
(13 19)
(17 23)
(23 29)
(31 37)
(37 43)
(41 47)
(47 53)
(53 59)
(61 67)
(67 73)
(73 79)
(83 89)
(97 103)

余談ですが、ウィキペディアで見ましたら、
セクシー素数５つ組が(5, 11, 17, 23, 29)　のただ一つ存在するそうです。
セクシー素数のセクシー組（６つ組）は存在しないそうです。
ーーーーーー4n+1型素数ーーーーーー
４ｎ＋１型素数とは初項１、等差４、の等差数列の中の素数であるものです。
例えば　(5 13 17 29 37 41 53 61 73 89 97)　です。
４ｎ＋３型素数は、初項３、等差４の等差数列の中の素数であるものです。
例えば、(3 7 11 19 23 31 43 47 59 67 71 79 83)　です。
｛４ｎ｝と｛４ｎ＋２｝は偶数になるので、素数は現れません。
（厳密に言うと、（４ｎ＋２｝に２のみ素数として現れます。）

次の定理があります。
公差が a である等差数列は、初項を 1 から（a − 1） の間に取るとき、
その初項が a と互いに素であるものが　φ(a) 通りある。
（φ(a) はオイラーの　φ関数である。）
これら　φ(a) 個の等差数列に素数はそれぞれほぼ均等に分布している

ａ＝４のとき　初項１、２，３にとるとき、
初項が４と素であるものは　１と３の２通りあり、
φ（４）＝２である。
初項と公差が互いに素である算術級数(等差数列)には無限に素数が存在する、
という定理をディリクレの算術級数定理と呼ぶそうです。
前置きが長くなりましたが、
４ｎ＋１型素数　と　４ｎ＋３型素数のどちらに素数が多く属するか、
Ｒａｃｋｅｔを使って素数の個数をカウントしてみます。
> (iota 25 1 4)　（４ｎ＋１型の等差数列　項数２５）
'(1 5 9 13 17 21 25 29 33 37 41 45 49 53 57 61 65 69 73 77 81 85 89 93 97)
> (filter prime? (iota 25 1 4))
'(5 13 17 29 37 41 53 61 73 89 97)　　（４ｎ＋１型の素数）
> (iota 25 3 4)　　　（４ｎ＋３型の等差数列）
'(3 7 11 15 19 23 27 31 35 39 43 47 51 55 59 63 67 71 75 79 83 87 91 95 99)
> (filter prime? (iota 25 3 4))
'(3 7 11 19 23 31 43 47 59 67 71 79 83)　　　（４ｎ＋３型の素数）
もう少しきちんとしたコードは次のとおりです。


(require (lib "1.ss" "srfi"))

      
(require math/number-theory)


(define (prime-list ls)

  (filter prime? ls))


(define (n-4-1-list n)

  (iota  n 1 4))　　　　　;;初項１、公差４、項数ｎの等差数列

      
(define (n-4-3-list n)

  (iota  n 3 4))　　　　　;;初項３、公差４、項数ｎの等差数列

      


(define (count ls)

  (count-sub 0 ls))


(define (count-sub a ls)

   (cond

      ((null? ls) a)

      (else (count-sub (+ 1 a) (cdr ls)))))


(count  (prime-list (n-4-1-list 100)))　－－－－→　３７

(count  (prime-list (n-4-3-list 100)))　ーーーー→　４０　

項数をそれぞれ１０００００にすると、
(count (prime-list (n-4-1-list 100000)))
16900
> (count (prime-list (n-4-3-list 100000)))
16959
ほぼ同じ素数の個数になりました。