210n+29 ,210n+31 ,210n+37 ,210n+41 ,210n+43 ,210n+47 ,
210n+53 ,210n+59 ,210n+61 ,210n+67 ,210n+71 ,210n+73 ,
210n+79 ,210n+83 ,210n+89 ,210n+97 ,210n+101,210n+103,
210n+107,210n+109,210n+113,210n+121,210n+127,210n+131,
210n+137,210n+139,210n+143,210n+149,210n+151,210n+157,
210n+163,210n+167,210n+169,210n+173,210n+179,210n+181,
210n+187,210n+191,210n+193,210n+197,210n+199,210n+209
Pについて表を作ってみました｡
図１ P値表
色が塗ってあるのは倍数で、色が塗ってないのがP値です｡2つの倍数の重なるものは大きいほうに塗ってあります｡
横が7なので,2の倍数は、上下には+6で並びます｡3の倍数も同じです｡右上から左下に並びます｡
5の倍数は+5で並ぶので2つおきに右上から左下に並びます｡
7の倍数は縦に並びます｡
P値は7(=7×1),35(=7×5),49(=7×7),77(=7×11),91(=7×13),119(=7×17),133(=7×19),161(=7×23),175(=7×25),203(=7×29)から始まり右上から左下へと並んでいます｡2,3の倍数は平行なので交わりませんが5の倍数と交わります｡
また、1,5(=5×1)を始値とする列もP値の値です｡
斜めのP値は5と7を始値とするものは間に3の倍数列が入ります｡７の下は2の倍数列、その下は3の倍数列その下は2の倍数列、その下はP値列になっています｡その下は,3の倍数列、その下はP値列です｡これの繰り返しです｡
7を始値とするものは右上から左下がりなので
7,13(=7+6)，19(=13+6),25(=19+6),31(=25+6),37(=31+6),43(=37+6)のように+6です。ただし，25は5の倍数です｡
よって，始値をNとするとN,N+6,N+12,N+18,N+24,N+30,N+36であり、
N+6L(ただしLは0≦L≦6の整数）とかけます｡
では、Nは、7(=7×1),35(=7×5),49(=7×7),77(=7×11),91(=7×13),119(=7×17),133(=7×19),161(=7×23),175(=7×25),203(=7×29)ですから
N= 7,
N= 35=7+7×4 =7×5,
N= 49=7+7×4+7×2 =7×7,
N= 77=7+7×4+7×2+7×4 =7×11,
N= 91=7+7×4+7×2+7×4+7×2 =7×13,
N=119=7+7×4+7×2+7×4+7×2+7×4 =7×17,
N=133=7+7×4+7×2+7×4+7×2+7×4+7×2 =7×19,
N=161=7+7×4+7×2+7×4+7×2+7×4+7×2+7×4 =7×23,
N=175=7+7×4+7×2+7×4+7×2+7×4+7×2+7×4+7×2 =7×25,
N=203=7+7×4+7×2+7×4+7×2+7×4+7×2+7×4+7×2+7×4=7×29,
これは,7×4と7×2を交互に足したものですね｡これは2と3の倍数を除いた式6M±1とすると
N=7×(6M±1)
となります｡
したがって、P=7(6M±1)＋6L(ただしLは0≦L≦6の整数）
P=7(6M±1)＋6L
=6(7M+L)±7
=42M+6L±7
=42M+(7-1)L±7
=42M+7(L±1)-L
となります｡ただし、5の倍数は除く｡
そこで,
P=42M+7(L±1)-L=5Q
42M+7(L±1)-L=5Q
で、Lは0≦L≦6の整数ですから,（5Qは1の位が0,5なので1の位のみに着目するとMはすぐ見つかる）
1)L=0のとき
42M+7(0±1)-0=42M±7=7(6M±1)＝5Qより、6M-1=5Wの時
ここで42M+7＜210となるMは0,1,2,3,4でありM=4のみである｡
ここで42M-7＜210となるMは0,1,2,3,4でありM=1のみである｡
2)L=1のとき
42M+7(1±1)-1=42M+6±7=5Q
より、
42M+7(1+1)-1=42M+13=5Q
ここで42M+13＜210となるM=0,1,2,3,4でありM=1のみである｡
また、
42M+7(1-1)-1=42M-1=5Q
42M-1=5Q
ここで42M-1＜210となるMは0,1,2,3,4でありM=3のみである｡
３）L=2のとき
42M+7(2±1)-2=42M+12±7=5Q
より、
42M+7(2+1)-2=42M+19=5Q
ここで42M-19＜210となるMは0,1,2,3,4でありM=2のみである｡
また、
42M+7(2-1)-2=42M+5=5Q
ここで42M+5＜210となるMは0,1,2,3,4でありM=0のみである｡
４）L=3のとき
42M+7(3±1)-3=5Q
より、
42M+7×(3+1)-3=42M*25=5Q
ここで42M+25＜210となるMは0,1,2,3,4でありM=0のみである｡
また、
42M+7×(3-1)-3=42M+11=5Q
ここで42M+11＜210となるMは0,1,2,3,4でありM=2のみである｡
５）L=4のとき
42M+7(4±1)-4=5Q
より、
42M+7×(4+1)-4=42M+31=5Q
ここで42M+31＜210となるMは0,1,2,3,4でありM=2のみである｡
また、
42M+7×(4-1)-4=42M+17=5Q
ここで42M+17＜210となるMは0,1,2,3,4でありM=4のみである｡
6）L=5のとき
42M+7(5±1)-5=5Q
より、
42M+7×(5+1)-5=42M+37=5Q
ここで42M+37＜210となるMは0,1,2,3であり満足するMはない｡
また、
42M+7×(5-1)-5=42M+23=5Q
ここで42M+23＜210となるMは0,1,2,3,4でありM=1のみである｡
7）L=6のとき
42M+7(6±1)-6=5Q
より、
42M+7×(6+1)-6=42M+43=5Q
ここで42M+43＜210となるMは0,1,2,3でありM=1のみである｡
また、
42M+7×(6-1)-6=42M+29=5Q
ここで42M+29＜210となるMは0,1,2,3,4でありM=3のみである｡
以上で,除かれる数は分かった｡
なお、N=5のものは,5+6L(ただしLは0≦L≦4の整数）でL=0のみ除かれます。
P=1も在ります｡
さて、以上を利用して210n+Pで素数でないものは
（210k+L)(210i+J)=（210n+m)
と表されることを証明しなければならない｡
【証明】
（210k+L)(210i+J)=210{210ki+(kJ+iL)}+LJ
ここでLJについて考えればよい｡
LJ={42m+7(u±1)-u}{42n+7(v±1)-v}
これより
LJ={42m+7(u+1)-u}{42n+7(v+1)-v}
LJ={42m+7(u+1)-u}{42n+7(v-1)-v}
LJ={42m+7(u-1)-u}{42n+7(v+1)-v}
LJ={42m+7(u-1)-u}{42n+7(v-1)-v}
の４とおりに分けられる｡
１）
LJ={42m+7(u+1)-u}{42n+7(v+1)-v}
=42m42n+42n7(u+1)-42nu+42m7(v+1)+7(u+1)7(v+1)-u7(v+1)-v42m-v7(u+1)+uv
=42{42mn+7n(u+1)-nu+7m(v+1)-mv}+7{7(u+1)(v+1)-u(v+1)-v(u+1)}+uv
=42{42mn+7nu+7n-nu+7mv+7m-mv}+7{7(uv+u+v+1)-uv-u-uv-v}+uv
=42{42mn+6nu+6mv+7m+7n}+7{7uv+7u+7v+7-uv-u-uv-v}+uv
=42{42mn+6nu+6mv+7m+7n}+7{5uv+6u+6v+7}+uv
=42x+35uv+42u+42v+49+uv
=42(x+u+v+1)+36uv+7
そこで
42x'+36uv+7=42a+7(b+1)-bとすると
42a+7(b+1)-b=42a+6b+7
42x'+36uv+7=42x'+6(6uv)+7=42a+6b+7
よって
LJ=42a+6b+7=42x'+6(6uv)+7
これで、１）の場合の
（210k+L)(210i+J)=（210n+m)
の証明終わり｡
２）
LJ={42m+7(u+1)-u}{42n+7(v-1)-v}
=42m42n+42n7(u+1)-42nu+42m7(v-1)+7(u+1)7(v-1)-u7(v-1)-v42m-v7(u+1)+uv
=42{42mn+7n(u+1)-nu+7m(v-1)-mv}+7{7(u+1)(v-1)-u(v-1)-v(u+1)}+uv
=42{42mn+7nu+7n-nu+7mv-7m-mv}+7{7(uv-u+v-1)-uv+u-uv-v}+uv
=42{42mn+6nu+7n+6mv-7m}+7{7uv-7u+7v-7-uv+u-uv-v}+uv
=42{42mn+6nu+7n+6mv-7m}+7{5uv-6u+6v-7}+uv
=42{42mn+6nu+7n+6mv-7m}+35uv-42u+42v-49+uv
=42{42mn+6nu+7n+6mv-7m}+36uv-42u+42v-49
=42{42mn+6nu+7n+6mv-7m-u+v-1}+36uv-7
=42x+36uv-7
そこで
42x+36uv-7=42a+7(b-1)-bとすると
42x+6(6uv)-7=42a+6b-7
よって
LJ=42a+6b-7=42x+6(6uv)-7
これで、2）の場合の
（210k+L)(210+J)=（210n+m)
の証明終わり｡
３）
LJ={42m+7(u-1)-u}{42n+7(v+1)-v}
=42m42n+42n7(u-1)-42nu+42m7(v+1)+7(u-1)7(v+1)-u7(v+1)-v42m-v7(u-1)+uv
=42{42mn+7n(u-1)-nu+7m(v+1)-mv}+7{7(u-1)(v+1)-u(v+1)-v(u-1)}+uv
=42{42mn+7nu-7n-nu+7mv+7m-mv}+7{7(uv-v+u-1)-uv-u-uv+v}+uv
=42{42mn+6nu-7n+6mv+7m}+7{7uv-7v+7u-7-uv-u-uv+v}+uv
=42{42mn+6nu-7n+6mv+7m}+7{5uv-6v+6u-7}+uv
=42{42mn+6nu-7n+6mv+7m}+35uv-42v+42u-49+uv
=42{42mn+6nu-7n+6mv+7m-v+u-1}+36uv-7
=42x+6(6uv)-7
よって
LJ=42a+6b-7=42x+6(6uv)-7
これで、3）の場合の
（210k+L)(210i+J)=（210n+m)
の証明終わり｡
４）
LJ={42m+7(u-1)-u}{42n+7(v-1)-v}
=42m42n+42n7(u-1)-42nu+42m7(v-1)+7(u-1)7(v-1)-u7(v-1)-v42m-v7(u-1)+uv
=42{42mn+7n(u-1)-nu+7m(v-1)-mv}+7{7(u-1)(v-1)-u(v-1)-v(u-1)}+uv
=42{42mn+7nu-7n-nu+7mv-7m-mv}+7{7(uv-u-v+1)-uv+u-uv+v}+uv
=42{42mn+6nu-7n+6mv-7m}+7{7uv-7u-7v+7-uv+u-uv+v}+uv
=42{42mn+6nu-7n+6mv-7m}+7{5uv-6u-6v+7}+uv
=42{42mn+6nu-7n+6mv-7m}+35uv-42u-42v+49+uv
=42{42mn+6nu-7n+6mv-7m-u-v+1}+36uv+7
=42x+6(6uv)+7
よって
LJ=42a+8b+7=42x'+8(8uv-7u-7v)+7
これで、4）の場合の
（210k+L)(210i+J)=（210n+m)
の証明終わり｡
【証明終わり】
よって、
（210k+L)(210i+J)=（210n+m)
となり、倍数は全て210n+Pの中に含まれる｡
以上の結果つぎのソフトができます｡
素数候補6000万個の中から1436万個の素数を18秒で求めます｡
エラトステネス篩法によるsosuu-5.tgz のダウンロード
sosuu-5.tgzの中身の説明
漢字コードの違いにより
sosuu-5.sjis.c シフトJISコード
sosuu-5.euc.c EUCコード
sosuu-5.utf.c UTF8コード
３つのCのソースプログラムが入っています｡
処理系の漢字環境で選択して下さい｡
つづく