Homeに戻る  一覧に戻る 

count twin primes in [sqrt(N)..N]

[2021.10.25]sqrt(N)以上N以下の双子素数の組数

■双子素数(Twin prime)

双子素数とは、(3,5), (5,7), (11,13), ...のように、差が2である２つの素数の組である。

■sqrt(N)以上N以下、または、5以上N以下の双子素数の組数を求めるプログラムを作成した。

5以上N以下の双子素数は、(6*m-1,6*m+1)の組に含まれるので、これらの形の整数のbit tableを作成して、5以上sqrt(N)以下の素数pで順に篩(いわゆるEratosthenesの篩)にかけて、残った(6*m-1,6*m+1)の組数を数える。

元々の目的は、sqrt(N)以上N以下の(6*m-1,6*m+1)の組について、篩にかける前の組数と、篩にかけた後の組数(残った組は双子素数になる)を比較することであった。

今回は必要メモリと実行速度を優先して、Cでプログラムを作成した。
64bit OSの環境では64bit版、32bit OSの環境では32bit版を推奨する。

■buildするには、gccを使って、以下のように実行する。

以下では、64bit OS(NetBSD-8.0/amd64)の環境で、64bit版の実行結果を紹介する。

[tp64.cのbuild方法とusage()の表示]
-bash-3.1$ gcc -O2 -lm tp64.c -o tp64
-bash-3.1$ ./tp64 -h
Usage: tp64
        endNumber       <= 103079215104 (malloc:4096MB)
        -o file         output primes to file
        -n              no-output (only total count)
        -p n            print n+n pairs of twin primes
        -s              print sieve process
        -h              help

■N=10^8について、N以下の双子素数の組数を数えてみる。
5以上10^8以下の双子素数は、440311組であり、これに(3,5)の１組を加えると、10^8以下の双子素数の組数は440312組であることが分かる。
また、10^8以下の最大の双子素数は(99999587,99999589)であることも分かる。

[tp64.cによる計算]
-bash-3.1$ time ./tp64 100000000
Succeded malloc (4166667 bytes).
start: size=4166667, pmint=10001, pmax=99999997
makeBitTable: 16665000 pairs in [10001. ... ,99999997]
end: psieve=9973
440107 twin primes in [10001..100000000].
440311 twin primes in [5..100000000].
 (99999587,99999589)

real    0m0.230s
user    0m0.220s
sys     0m0.010s

■64bit版のCプログラムでは、5以上10^11以下までの双子素数の組数を数えることができる。
その実行結果をまとめると、以下のようになる。
ただし、表タイトルの中の、{sqrt(N)}はmin{q : qは素数, q^2<=N }、すなわち、sqrt(N)以上の最小の素数とする(ここだけの略記法)。

n N=10^n V=#{(6*m-1,6*m+1)
∈[{sqrt(N)}..N]2 : mは自然数}
篩にかける前の(6*m±1)の組数		 U=#{(p,p+2)
∈[{sqrt(N)}..N]2 : pは素数}
篩にかけた後(双子素数)の組数		 U/V

全ての素数
p∈[5..[sqrt(N)]]で
篩をかけて残った組の
比率		 Uの最小の双子素数
[>=sqrt(N)]		 Uの最大の双子素数
[<=N]		 #{(p,p+2)∈[3..N]2 : pは素数}
N以下の双子素数の組数
[(3,5)を含む]
2 100 15 6 0.40000000000000000 (11, 13) (71, 73) 8
3 1000 161 30 0.18633540372670807 (41, 43) (881, 883) 35
4 10000 1650 197 0.11939393939393939 (101, 103) (9929, 9931) 205
5 100000 16614 1204 0.07246900204646683 (347, 349) (99989, 99991) 1224
6 1000000 166500 8134 0.04885285285285285 (1019, 1021) (999959, 999961) 8169
7 10000000 1666140 58897 0.03534937040104673 (3167, 3169) (9999971, 9999973) 58980
8 100000000 16665000 440107 0.02640906090609060 (10007, 10009) (99999587. 99999589) 440312
9 10000000000 166661396 3424019 0.02054476370760748 (31721, 31723) (999999191, 999999193) 3424506
10 100000000000 1666650000 27411455 0.01644703747037470 (100151, 100153) (9999999701, 9999999703) 27412679
11 1000000000000 16666613962 224372915 0.01346241747193352 (316241, 316243) (99999999761, 99999999763) 224376048

■命題TP1(A,B)を「A以上B以下の双子素数が(1組以上)存在する」とする。
上記の表を見る限りでは、以下のような予想ができる。

     (予想TP2) 任意のN>=100に対して、TP1(sqrt(N),N)である。

しかし、Nをもっと大きくしてもTP1(sqrt(N),N)が成立するのかどうかは分からないし、仮に(予想TP2)が正しいとしても、簡単には証明できそうにない。

■1000桁以上の双子素数をどれでもいいから、１組見つけるように要望されたら、簡単なプログラムを作成して、(運任せではあるが)時間を掛けると探すことができる。

例えば、
p=539968231392637176594991699564830875981668514048278618683489980439388444083721380209028775273034092569648903905780330615761566787894357414062117067081378929251743540280607405527112003822753186725873339963921032994489581186328877335948848218028658179866360642871377073691350300065897687781715169154804582788612595307604025242219447847021805655519777558452328085402368127225181096236637296406973718952544565153776323987214504182654524509420575105737731894061404423609530014624838802246881504089220239808446007581785620600074984808012383748940673323581581450059321436370284298564144399886653741742259307699667423047935765222361040473475857453651738926903807332876992730078191871666226033929688825464950878108463940454112455510589419831763726785821056710105316985253464952957164347535489666025525848577505464780946685606053265546477461401338802621563502314506544081755527118197715997783111163938857955622334499912120088838159625439923120713734499852204261755165382913577187619204604569795113618677110440357

p+2=539968231392637176594991699564830875981668514048278618683489980439388444083721380209028775273034092569648903905780330615761566787894357414062117067081378929251743540280607405527112003822753186725873339963921032994489581186328877335948848218028658179866360642871377073691350300065897687781715169154804582788612595307604025242219447847021805655519777558452328085402368127225181096236637296406973718952544565153776323987214504182654524509420575105737731894061404423609530014624838802246881504089220239808446007581785620600074984808012383748940673323581581450059321436370284298564144399886653741742259307699667423047935765222361040473475857453651738926903807332876992730078191871666226033929688825464950878108463940454112455510589419831763726785821056710105316985253464952957164347535489666025525848577505464780946685606053265546477461401338802621563502314506544081755527118197715997783111163938857955622334499912120088838159625439923120713734499852204261755165382913577187619204604569795113618677110440359

は、どちらも1002桁の素数であり、その差は2であるので、1000桁以上の双子素数である。

これにより、TP1(10^1000,10^2000)が成立することが分かる。
しかし、2000桁以上の双子素数はすぐには見つからないので、TP1(10^2000,10^4000)は正しそうではあるが、本当に正しいのかどうかは簡単には分からない。
ましてや、これらの情報からは、(予想TP2)が正しいのかどうかは、全く分からない。

[参考文献]

Last Update: 2021.11.03
H.Nakao

Homeに戻る[Homeに戻る]  一覧に戻る[一覧に戻る]