私の自分史習作

以前にHPを作っていました。
それも含めた身辺雑記エッセイです。
最近はRacketプログラムや本の紹介です。

フェルマー素数ーRacketを使って

2017-05-17 20:00:16 | Weblog
メルセンヌ素数と似ていますが、フェルマー素数を取り上げます。
メルセンヌ素数は、次のようになります。
M_n (P) = 2^p - 1 の形で pは素数で M_n (p) も素数の場合です。

フェルマー素数は、次のようになります。
F_n (n) = 2^(2^n) + 1 の形で F_n (n) が素数のものです。

Racketのプログラムは次のようになります。

(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)
>
最初の5項のみ 3 5 17 257 65537 のみフェルマー素数で #t が表示されます。
n が5 の時の 4294967297 は素数ではなくて #f が表示されます。
(divisors 4294967297)
'(1 641 6700417 4294967297)
となり、641 × 6700417
素因数分解されます。



ジャンル:
ウェブログ
コメント   この記事についてブログを書く
この記事をはてなブックマークに追加
« 三つ子素数について-Rac... | トップ | セクシー素数ーRacket... »

コメントを投稿


コメント利用規約に同意の上コメント投稿を行ってください。

数字4桁を入力し、投稿ボタンを押してください。

あわせて読む

トラックバック

この記事のトラックバック  Ping-URL