|
|
問題
異なる６つの素数が書かれた同じ２つのサイコロがある。
２つのサイコロを振ると必ず２つの出た目の相加平均が素数になるという。
さて、そのサイコロに書かれている６個の素数とは？
考察
素数は、2,3,6k-1,6k+1に分類される。
平均が素数にならないといけないので、2は不適である。
また、6k-1と6k+1とでは6kになるので、この組み合わせも不適である。
したがって、以下のような組み合わせだけが考えられる。
・3と5つの6k-1の場合
・3と5つの6k+1の場合
・6つの6k-1の場合
・6つの6k+1の場合
（終わり）
LET t0=TIME
LET MX=168 !個数 ※
DIM P(MX)
LET P(1)=3 !3,6k-1型
LET N=P(1)
LET C=1
DO WHILE C<MX
LET C=C+1
DO
LET N=NextPrime(N)
LOOP UNTIL MOD(N,6)=5 !6k-1型 ※
LET P(C)=N !次の素数へ
LOOP
MAT PRINT P; !debug
DIM A(6)
FOR X=MX TO 6 STEP -1 !検索する範囲はx番目から
LET A(1)=P(X)
CALL try(X-1,2,MX,P,A)
NEXT X
PRINT TIME-t0
END
EXTERNAL SUB try(X,N,MX,P(),A()) !バックトラック法で検索する
IF N>6 THEN !6つの目がそろったら
MAT PRINT A;
ELSE
DO WHILE X>0
FOR i=1 TO N-1 !前出の目との組み合わせ
IF PrimeQ( (A(i)+P(X))/2 )=0 THEN EXIT FOR
NEXT i
IF i>N-1 THEN !題意を満たす
LET A(N)=P(X)
CALL try(X-1,N+1,MX,P,A) !次の目へ
END IF
LET X=X-1 !次の素数へ
LOOP
END IF
END SUB
!試行割算法（2,3,12m±1,12m±5）
EXTERNAL FUNCTION PrimeQ(n) !素数判定 1:素数、0:素数でない
LET PrimeQ=0
IF n<2 OR n<>INT(n) THEN EXIT FUNCTION !引数を確認する
!２以上の自然数なら
IF MOD(n,2)=0 THEN !２の倍数
IF n=2 THEN LET PrimeQ=1 !２は素数
ELSEIF MOD(n,3)=0 THEN !３の倍数
IF n=3 THEN LET PrimeQ=1 !３は素数
ELSEIF MOD(n,5)=0 THEN !５の倍数
IF n=5 THEN LET PrimeQ=1 !５は素数
ELSEIF MOD(n,7)=0 THEN !７の倍数
IF n=7 THEN LET PrimeQ=1 !７は素数
ELSEIF MOD(n,11)=0 THEN !11の倍数
IF n=11 THEN LET PrimeQ=1 !11は素数
ELSE
LET k=13
DO WHILE k*k<=n !√nまで検証する
IF MOD(n,k)=0 THEN EXIT FUNCTION !13,25,37,49,61,…
IF MOD(n,k+4)=0 THEN EXIT FUNCTION !17,29,41,53,65,…
IF MOD(n,k+6)=0 THEN EXIT FUNCTION !19,31,43,55,67,…
IF MOD(n,k+10)=0 THEN EXIT FUNCTION !23,35,47,59,71,…
LET k=k+12
LOOP
LET PrimeQ=1 !最後まで割り切れなければ、素数である
END IF
END FUNCTION
EXTERNAL FUNCTION NextPrime(n) !nより大きい素数の最小のもの
IF n<2 THEN
LET NextPrime=2
ELSEIF n<3 THEN
LET NextPrime=3
ELSEIF n<5 THEN
LET NextPrime=5
ELSEIF n<7 THEN
LET NextPrime=7
ELSEIF n<11 THEN
LET NextPrime=11
ELSE
LET k=INT((n-13)/12)*12+13 !12m±1、12m±5
DO
IF k>n THEN !見つかるまで
LET NextPrime=k
IF PrimeQ(k)<>0 THEN EXIT DO
END IF
IF k+4>n THEN !見つかるまで
LET NextPrime=k+4
IF PrimeQ(k+4)<>0 THEN EXIT DO
END IF
IF k+6>n THEN !見つかるまで
LET NextPrime=k+6
IF PrimeQ(k+6)<>0 THEN EXIT DO
END IF
IF k+10>n THEN !見つかるまで
LET NextPrime=k+10
IF PrimeQ(k+10)<>0 THEN EXIT DO
END IF
LET k=k+12 !次へ
LOOP
END IF
END FUNCTION
実行結果
：
：
509 449 113 53 29 5
509 353 269 113 29 5
491 467 311 227 71 47
479 443 419 83 59 3
479 443 83 59 23 3
461 257 101 41 17 5
449 353 269 113 29 5
449 269 113 89 29 5
449 173 89 53 29 5
449 113 89 53 29 5
443 251 83 23 11 3
443 191 83 23 11 3
443 191 71 23 11 3
383 251 131 83 11 3
補足
実際には、型の区別をせず奇素数から6つ選べばよい。
LET MX=168 !個数 ※
DIM P(MX) !3,6k±1
LET N=2
LET C=0
DO WHILE C<MX
LET C=C+1
LET N=NextPrime(N)
LET P(C)=N !次の素数へ
LOOP
MAT PRINT P; !debug
：
|
|