ユークリッドの証明[br][br]たとえば、[br]２の倍数に１をたした数は２の倍数ではない。[br]３の倍数に１をたした数は３の倍数ではない。[br]５の倍数に１をたした数は５の倍数ではない。[br]これはだれもが認める事実です。[br][br][b][size=150]＜ユークリッドさん＞[/size][/b][br]ユークリッドはこれらの事実を利用します。[br]2×3×5は２、３、５の倍数ですから、[br]2×3×5＋１は、２の倍数でも、３の倍数でも、５の倍数でもないことになります。[br]ユークリッド「原論」の論法はこうでした。[br]素数が有限個しかなく、そのリストが２，３、...、ｐのように、ｐで終わるとする。[br]N＝２×３×…×ｐ＋１は、すべての素数２からｐで割り切れません。[br]つまりNは素数を使って合成できないので、Nは素数です。[br]しかし、Nは素数リストの最大数ｐより大きいので、矛盾します。[br]だから、素数は有限個とする仮定が誤りだから、素数は無限にある。[br][br]このユークリッドさんの論法は現実離れしてますね。[br]そもそも、すべての素数という物自体が確定できないのに、それを仮定する思考だからです。[br]プログラミングしようとしても、すべての素数の集合は作れないので計算不可能ですね。[br]本当に神の視点に立った論理ですね。[br][br]たとえば、素数＝ [2,3,5,7,11,13,17,19,23]。[br]これがすべての素数だとして、Nを計算するとNは合成数になってしまいます。[br]「すべての素数」といっておきながら、途中の素数をすっとばして、[br]でかいNを作っているわけですから、Nが素数にならない可能性が出てきますね。[br]だから、この「すべての素数」という、現実的には、できもしないことを前提にした論理ですから、[br]現実の有限数でたしかめようとしても破綻しますね。[br]無限個なものを有限とあえて偽っているのですから。[br][br][color=#0000ff][IN]Python[br]#Euclid[br]from sympy import isprime[br]from [url=https://www.geogebra.org/m/twxxx3yq#material/jetureys]operator[/url] import mul[br]from [url=https://www.geogebra.org/m/twxxx3yq#material/gjpwuajn]functools[/url] import reduce[br][br]def prime_euc():[br] Ps = [2,3,5,7,11,13,17,19,23][br] [b]N = reduce(mul,Ps)+1[/b][br] print([b]isprime(N)[/b],end=":")[br] print([b]get_divisors(N)[/b])[br] Ps = Ps + [N][br] return Ps[br]print(prime_euc())[/color][br][b][OUT][br]False:[1, 317, 703763, 223092871][br][2, 3, 5, 7, 11, 13, 17, 19, 23, 223092871][br][/b][b]223092871は素数ではないが、最小の素因数317はPsの最大の素数23より大きい。[br][/b]ここに着目すれば、少数の素数リストからスタートして、素数を追加することはできそうだ。[br][br][br][size=150][b]＜ピタゴラスとマリンさん＞[br][/b][/size]ユークリッドの証明法のルーツはピタゴラスの論法だという説があります。[br]その論法を明確化して、おまけをつけたマリンという人がいます。[br]素数リストをPsとしましょう。[br][b]（ベース）Psに2を入れます。[br]（反復）N=（Psにあるすべての素数の積）＋１。Nの１より大きい最小約数MをPsに加える。[br][/b]MがPsの素数とかぶらないので、この反復は無限に続きますから、素数は無限リストになります。[br][br]「[color=#0000ff]順番はともかくこのリストにすべて素数が入る[/color]」という仮説があります。[br][br][color=#9900ff][b][u][size=150]課題：ピタゴラス・マリンの素数列をつくるにはどうしたらよいですか。[br][/size][/u][/b][/color][br]ジェネレータや関数プログラミングツールを使うことで、日本語をただ英語に直す感じで[br]コードをかいてみよう。[br][br][color=#0000ff][IN]Python[br][/color][color=#0000ff]from operator import mul[br]from functools import reduce[br]def prime_seq():[br] [b]Ps [/b]= [2][br] while True:[br] [url=https://www.geogebra.org/m/twxxx3yq#material/nwyj8w4m]yield [/url][b]Ps[/b][br] N = reduce(mul,Ps)+1[br] for i in range(2, N+1):[br] if N % i == 0:[br] [b]M [/b]= i # Mは1より大きいNの最小約数で、素数[br] break [br] [b]Ps = Ps + [M][/b][br][br]generator = prime_seq()[br]for _ in range(8):[br] print(next(generator))[br][/color][OUT][br][b][2][br][2, 3][br][2, 3, 7][br][2, 3, 7, 43][br][2, 3, 7, 43, 13][br][2, 3, 7, 43, 13, 53][br][2, 3, 7, 43, 13, 53, 5][br][2, 3, 7, 43, 13, 53, 5, 6221671][/b][br][br]９ステップ目になかなかいかないので、sympyにたよってみよう。[br][br][color=#0000ff][IN]Python[br][/color][color=#0000ff]from functools import reduce[br]from operator import mul[br][b]from sympy import factorint[br][/b]def prime_seq_fast():[br] Ps = [2][br] while True:[br] yield Ps[br] N = reduce(mul, Ps) + 1[br] # factorint(N) は {素因数: 個数} の辞書を高速に返します[br] [b]factors = factorint(N)[/b][br] # 最小の素因数（最小の約数 M）を取得[br] [b]M = min(factors.keys())[/b][br] Ps = Ps + [M][br][br]generator = prime_seq_fast()[br]# 少し多めに回してみます[br]for i in range(17):[br] print(f"Step {i+1}: {next(generator)}")[br][/color][OUT][br][b]Step 1: [2][br]Step 2: [2, 3][br]Step 3: [2, 3, 7][br]Step 4: [2, 3, 7, 43][br]Step 5: [2, 3, 7, 43, 13][br]Step 6: [2, 3, 7, 43, 13, 53][br]Step 7: [2, 3, 7, 43, 13, 53, 5][br]Step 8: [2, 3, 7, 43, 13, 53, 5, 6221671][br]Step 9: [2, 3, 7, 43, 13, 53, 5, 6221671, 38709183810571][br]Step 10: [2, 3, 7, 43, 13, 53, 5, 6221671, 38709183810571, 139][br]Step 11: [2, 3, 7, 43, 13, 53, 5, 6221671, 38709183810571, 139, 2801][br]Step 12: [2, 3, 7, 43, 13, 53, 5, 6221671, 38709183810571, 139, 2801, 11][br]Step 13: [2, 3, 7, 43, 13, 53, 5, 6221671, 38709183810571, 139, 2801, 11, 17][br]Step 14: [2, 3, 7, 43, 13, 53, 5, 6221671, 38709183810571, 139, 2801, 11, 17, 5471][br]Step 15: [2, 3, 7, 43, 13, 53, 5, 6221671, 38709183810571, 139, 2801, 11, 17, 5471, 52662739][br]Step 16: [2, 3, 7, 43, 13, 53, 5, 6221671, 38709183810571, 139, 2801, 11, 17, 5471, 52662739, 23003][br]Step 17: [2, 3, 7, 43, 13, 53, 5, 6221671, 38709183810571, 139, 2801, 11, 17, 5471, 52662739, 23003, 30693651606209][br][/b][br]すざまじい素数の波ですね。津波がきたとおもったら、やさしいさざ波になったり、また大波だ。
素数の隙間と言えば[br][url=https://www.geogebra.org/m/twxxx3yq#material/gppvzzjw]双子素数[/url]が有名だ。[br]３と５[br]１１と１３[br]１７と１９[br]のように、素数が最低の隙間、１つの整数があく２つの素数だ。[br]ではその反対、素数の空白地帯を考えてみよう。[br]２×３×５+2=32[br]２×３×５+3=33[br]２×３×５+4=34[br]２×３×５+5=35[br]２×３×５+6=36[br]２×３×５×７+2 =212[br]２×３×５×７+3 =213[br]２×３×５×７+4 =214[br]２×３×５×７+5 =215[br]２×３×５×７+6 =216[br]２×３×５×７+7 =217[br]２×３×５×７+8 =218[br]２×３×５×７+9 =219[br]２×３×５×７+10=220[br][color=#9900ff][b][u][size=150]課題：素数の隙間をもっと長く作るにはどうしたらよいでしょうか。[br][br][/size][/u][/b][/color]たとえばｐを1009にすると、2から1001までの整数は素数リスト（2から1009）のどれかで割り切れますね。だから、N=product(２から1009)として、iをrange(2,1002)で動かしたN+iは素数になりません。[br]でも、これだと1000個の非素数列ができますが、長すぎます。[br]100個を出すコードを作ってみよう。[br][color=#0000ff][IN]Python[br]from sympy import isprime[br]from operator import mul[br]from functools import reduce[br]def primefree():[br][b] N = reduce(mul,Target)[br][/b] for i in range(2,101):[br][b] nonP = N + i [br] judge = isprime(nonP)[br] print(nonP, judge)[br][/b] return res[br]Target=[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47][br]print(Target)[br]primefree()[br][/color][OUT][br]#[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47][br]614889782588491412 False[br]614889782588491413 False[br]614889782588491414 False[br]614889782588491415 False[br]614889782588491416 False[br]614889782588491417 False[br]614889782588491418 False[br]614889782588491419 False[br]614889782588491420 False[br]614889782588491421 False[br]614889782588491422 False[br]614889782588491423 False[br]614889782588491424 False[br]614889782588491425 False[br]614889782588491426 False[br]614889782588491427 False[br]614889782588491428 False[br]614889782588491429 False[br]614889782588491430 False[br]614889782588491431 False[br]614889782588491432 False[br]614889782588491433 False[br]614889782588491434 False[br]614889782588491435 False[br]614889782588491436 False[br]614889782588491437 False[br]614889782588491438 False[br]614889782588491439 False[br]614889782588491440 False[br]614889782588491441 False[br]614889782588491442 False[br]614889782588491443 False[br]614889782588491444 False[br]614889782588491445 False[br]614889782588491446 False[br]614889782588491447 False[br]614889782588491448 False[br]614889782588491449 False[br]614889782588491450 False[br]614889782588491451 False[br]614889782588491452 False[br]614889782588491453 False[br]614889782588491454 False[br]614889782588491455 False[br]614889782588491456 False[br]614889782588491457 False[br]614889782588491458 False[br]614889782588491459 False[br]614889782588491460 False[br]614889782588491461 False[br]614889782588491462 False[br]614889782588491463 False[br]614889782588491464 False[br]614889782588491465 False[br]614889782588491466 False[br]614889782588491467 False[br]614889782588491468 False[br]614889782588491469 False[br]614889782588491470 False[br]614889782588491471 False[br]614889782588491472 False[br]614889782588491473 False[br]614889782588491474 False[br]614889782588491475 False[br]614889782588491476 False[br]614889782588491477 False[br]614889782588491478 False[br]614889782588491479 False[br]614889782588491480 False[br]614889782588491481 False[br]614889782588491482 False[br]614889782588491483 False[br]614889782588491484 False[br]614889782588491485 False[br]614889782588491486 False[br]614889782588491487 False[br]614889782588491488 False[br]614889782588491489 False[br]614889782588491490 False[br]614889782588491491 False[br]614889782588491492 False[br]614889782588491493 False[br]614889782588491494 False[br]614889782588491495 False[br]614889782588491496 False[br]614889782588491497 False[br]614889782588491498 False[br]614889782588491499 False[br]614889782588491500 False[br]614889782588491501 False[br]614889782588491502 False[br]614889782588491503 False[br]614889782588491504 False[br]614889782588491505 False[br]614889782588491506 False[br]614889782588491507 False[br]614889782588491508 False[br]614889782588491509 False[br]614889782588491510 False
等差数列といえば、[br]初項と公差が同じである「倍数の数列」からみれば、[br]等差数列は初項と公差が一致するとはかぎらない。[br]言い換えると、倍数の数列をずらしたものだ。[br][br]たとえば、「３の倍数」の数列を[url=https://www.geogebra.org/m/raktcqcy#material/ysmpkap2]エラトステネスのふるい[/url]と比べてみよう。[br][b]３[/b]，６，９，１２，１５、……………[br]エラトステネスのふるいでは「[b]３だけ残して、あと数列の残党はバッサリ[/b]」捨てられている。[br]素数の倍数列では素数は先頭しかない。[br]合成数の倍数列ではどうだろう。「[b]まるごと捨て[/b]」られる。[br]４，８，１２，１６，２０、…………[br][br]それにくらべて等差数列はどうだろう。[br]うまく、エラトステネスのふるいから「[b]丸ごと捨てられるような無残なこと[/b]」にはならない。[br][br]それどころか、[b]けっこう素数が出現[/b]する。ところどころ捨てられても[b]生き残りが多数[/b]ありそうだ。[br]けっこうどころか[b]無限に素数がある[/b]というのだ。[br][br][b][size=150]＜３で割った余りが２の数列＞[br][/size][/b][br]３で割って１余る数列をS1と書きしょう。[br][b]S1＝[/b]｛１，4，[b]7[/b]，１0，[b]１3[/b]，１6、[b]１９[/b]，２２，２５，２８，[b]３１[/b]，３４、………｝[br]素数は７，１３，１９，３１，…と出現しますね。[br][br]３で割って２余る数列をS2と書きしょう。[br][b]S2=｛２[/b]，[b]５[/b]，８，[b]１１[/b]，１４，[b]１７[/b]、２０，[b]２３[/b]，２６，[b]２９[/b]，３２，３５、………｝[br]素数は２，５，１１，１７，２３，２９、…とわりと多く出現しますね。[br][br]合成数に目をつけましょう。[br]S1の４＝[b]2[/b]^2、10＝[b]２[/b]×[b]5[/b]、16＝[b]2[/b]^4、22＝[b]2[/b]×[b]11[/b]、25＝[b]5[/b]^2、28＝[b]2[/b]^2*7, 34=[b]２[/b]×[b]17[/b],....[br]S2の８＝[b]2[/b]^3、14＝[b]2[/b]×7、20＝[b]2[/b]^2*5, 26=[b]2[/b]×13、32＝[b]2[/b]^5, 35＝[b]５[/b]×7[br]合同式で考えると、S2の要素=-1(mod 3)、S1の要素=1(mod 3)です。[br]１は何個かけても１と合同ですが、－１を作るにはー１を奇数個かけないといけません。[br]１をー１と１をまぜて作るにはー１を偶数個かけないといけません。[br]だから、[br]S１の合成数を見ると、S２の素数を偶数個かけてます。[br]S２の合成数を見ると、S２の素数を1個以上の奇数個かけてます。[br][br]さて、ここで、２からｐまでの素数の積をNとしましょう。[br]Nは３の倍数ですね。[br]だからM１＝N+1、M2=N-1とすると、M1はS1に登場し、M2はS2に登場する巨大数ですね。[br][br]ユークリッド、ピタゴラスの素数無限論で登場するのはM1型でしたね。[br][b]Ps＝[2, 3, 5, 7, 11, 13, 17, 19, 23]と最大をp=23としてN＝product(Ps)+1としたとき、[br][/b][b]N=223092871は素数ではないが、最小の素因数317はPsの最大の素数23より大きかった。[br][/b]ここに着目すれば、少数の素数リストからスタートして、素数を追加することはできた。[br]それが、マリンのアルゴリズムだった。[br]M1型の発想で作ったNはS1に属するけれど、Nの素因数がS1に続するかどうかは不明だね。[br][br][br]M２型ならどうでしょう。M2が素数ならｐより大きい素数があるということになります。[br]M２が合成数ならどうでしょうか。NはS2型だからNの素因数にS２型が1個はあるはずです。[br]つまり、S2には素数は無限に入るということだね。[br][br][b][u][color=#9900ff][size=150]課題：S２型の素数が無限に作られるコードにとりくんでみよう。[br][/size][/color][/u][/b][br]土台になる素数リストはS2型に限定しなくてもいいです。[br]新しく追加された素数をS2型としましょう。[br][br][color=#0000ff]#S2type-mullin[br]from functools import reduce[br]from operator import mul[br]from sympy import factorint[br]def s2_prime_generator():[br] Ps = [2, 3, 5] # S1,S2に関係なく土台として使う素数リスト[br] Start = Ps[br] S2 =[][br] while True:[br] yield S2[br] # M2型: これまでの積 - 1[br] M2 = reduce(mul, Ps) - 1[br] factors = factorint(M2).keys()[br][b] M = min([f for f in factors if f % 3 == 2]) #S2型の最小素因数[br][/b] Ps = Ps + [M][br] S2 = [x for x in Ps if x not in Start][br]# 探検隊、M2型のルートで8ステップ追跡[br]generator = s2_prime_generator()[br]for i in range(8):[br] current_list = next_generator = next(generator)[br] print(f"Step {i+1}: {current_list}")[br][/color][OUT][br][b]Step 1: [][br]Step 2: [29][br]Step 3: [29, 11][br]Step 4: [29, 11, 1367][br]Step 5: [29, 11, 1367, 13082189][br]Step 6: [29, 11, 1367, 13082189, 89][br]Step 7: [29, 11, 1367, 13082189, 89, 59][br]Step 8: [29, 11, 1367, 13082189, 89, 59, 29819952677][/b]
[b][size=150]＜３で割った余りが１の数列＞[/size][/b][br][br]では、３で割った余りが１の数列、S1に無限の素数があるだろうか。[br]最初に書き出した、S1とS2の数列をみてみよう。[br][b]S1＝[/b]｛１，4，[b]7[/b]，１0，[b]１3[/b]，１6、[b]１９[/b]，２２，２５，２８，[b]３１[/b]，３４、………｝[br][b]S2=｛２[/b]，[b]５[/b]，８，[b]１１[/b]，１４，[b]１７[/b]、２０，[b]２３[/b]，２６，[b]２９[/b]，３２，３５、………｝[br]素数がS1とS2をほぼ、交互にいったりきたりしているようだから、S２だけに素数が無限にあるのも[br]違う気がする。[br][br]ユークリッド、ピタゴラスの素数無限論で登場するM1型の実験を思い出そう。[br][br][b]Ps＝[2, 3, 5, 7, 11, 13, 17, 19, 23]と最大をp=23としてN＝product(Ps)+1としたとき、[br][/b][b]N=223092871は素数ではないが、最小の素因数317はPsの最大の素数23より大きかった。[br]それで、317を素数リストPsに追加したね。[br]しかし、[/b]S1とS2に分けていなかったから、よかったけれど、[b]317は3で割った余りは２だから使えない。[br][/b][b]703763もよく見ると３で割った余りは２だ。223092871は素数でない。[br][/b]ということは、Psを土台にして、S1の先を作ろうとしたのだが、いきなり破綻した。[br]そこで、Nをユークリッド式の1次式にするのをやめる。[br][br]整数を３で割った余りで分類しているから、群としては｛0，1，2｝という剰余類になる。[br][url=https://www.geogebra.org/m/twxxx3yq#material/ywpwfh5a]剰余群は巡回群[/url]になるから、複素平面の円周の3等分点と同型になる。だから、z^3=1となる。[br]ｚ^3-1=(z-1)(z^2+z+1)と分解できて、ｚ＝１では動きがない。[br]だから、z^2+z+1と同型にしたらどうだろうか。[br]たとえば、t=[b]product(Ps)とするとき、N=ｔ＋１ではなく、N=t^2+t+1にするのだ。[br][/b]検証しやすく土台はPs=[2,3,5]にしてみよう。[br]tは３の倍数だから、Nは素数かどうかは別として余り１だ。Nの素因数で余り１を追加していこう。[br]最初はｔ＝２×3×5＝30、N＝931。よさそうだね。[br][br][color=#9900ff][b][u][size=150]課題：３で割って１余る数列で無限に素数を作るコードにとりくもう。[br][/size][/u][/b][/color][br][IN]Python[br]#S1type-mullin[br]from functools import reduce[br]from operator import mul[br]from sympy import factorint[br]def s1_prime_generator():[br] Ps = [2, 3, 5] # S1,S2に関係なく土台として使う素数リスト[br] Start = Ps[br] S1 =[][br] while True:[br] yield S1[br] # 2次の生成式[br] t = reduce(mul, Ps)[br] N = t**2 + t + 1[br] factors = factorint(N).keys()[br] M = min([f for f in factors if f % 3 == 1]) #S1型の最小素因数[br] Ps = Ps + [M][br] S1 = [x for x in Ps if x not in Start][br]# 探検隊、S1型のルートで8ステップ追跡[br]generator = s1_prime_generator()[br]for i in range(10):[br] current_list = next_generator = next(generator)[br] print(f"Step {i+1}: {current_list}")[br][OUT][br][b]Step 1: [][br]Step 2: [7][br]Step 3: [7, 73][br]Step 4: [7, 73, 13][br]Step 5: [7, 73, 13, 163][br]Step 6: [7, 73, 13, 163, 43][br]Step 7: [7, 73, 13, 163, 43, 1006867933][br]Step 8: [7, 73, 13, 163, 43, 1006867933, 607][br]Step 9: [7, 73, 13, 163, 43, 1006867933, 607, 1117][br]Step 10: [7, 73, 13, 163, 43, 1006867933, 607, 1117, 909309821128128549785509674722967283825203785371][br][/b][br]よい感じで波打って出力できました。[br][br][b][size=150]＜振り返り＞[br][/size][/b]なぜ、N = t^2 + t + 1がS1型の素数ｐしか生まないのだろうか。[br][br]ある素数ｐがNを割り切るとしたら、N[url=https://www.geogebra.org/m/twxxx3yq#material/wud5mfpc]≡０（modp)[/url]とかけるね。[br]t^2 + t + 1≡０（modp)の両辺にt-1をかけると、t^3-1≡0(modp)となる。[br][br]これは、ｔの3乗がmod pでは1と合同だから、[br]ｔは3乗して1になる周期（位数3）を持つということだね。[url=https://www.geogebra.org/m/twxxx3yq#material/jee2nn3r][br]フェルマーの小定理[/url]（ｔ[sup]p-1[/sup] ≡1 (mod p)）から、[b]p-1 が 3 の倍数でなければならないと言える。[br][/b]これから素数pは３の倍数＋１なので、S1に追加できたわけだ。[br][br][color=#9900ff][b][u][size=150]課題：geogabraを使って、マリン数列が作れるでしょうか。[br][/size][/u][/b][/color][b][br]Step 9: [2, 3, 7, 43, 13, 53, 5, 6221671, 38709183810571][br][/b][br]iterationListがうまく動くかわからないのと、[br]もともと6221671のあとにけた数が爆発するので、手動でいいでしょう。[br]a=Element(divisors(product({2,3})+1),2)[br]b=Element(divisors(product({2,3,7})+1),2)[br]c=Element(divisors(product({2,3,7,43})+1),2)[br]d=Element(divisors(product({2,3,7,43,13})+1),2)[br]e=Element(divisors(product({2,3,7,43,13,53})+1),2)[br][b]f=Element(divisors(product({2,3,7,43,13,53,5})+1),2)[br][/b]