プログラム依頼

 投稿者：GAI  投稿日：2016年 3月30日(水)10時00分7秒
  連続するn個の自然数を円形に配置し、どの隣り合う２つの数の和が素数になる配列を作って実験していたら
１～４ならそのままテーブルに1,2,3,4 と配置すれば２つの和が3,5,7,5(1+4)となり条件を満たす。
１～６なら1,4,3,2,5,6と並ぶと和は5,7,5,7,11,7 ですべて素数
１～８なら1,4,7,6,5,8,3,2とすれば,5,11,13,11,13,11,5,3 となりやはり可能
ところが
１～５、１～７でいくら試していてもそのような配置が不可能であるみたいなのです。（もしかしたら存在するのか断定はできかねるが・・・）
そこで一般に１～ｎの数字を円形に並べたとき、どの隣の２数の和が素数になるような配列を求めるプログラムを構成して頂きたいのですが、よろしくお願いします。

 		 

Re: プログラム依頼

 投稿者：山中和義  投稿日：2016年 3月30日(水)12時04分38秒
  > No.4021[元記事へ]

GAIさんへのお返事です。

> １～５、１～７でいくら試していてもそのような配置が不可能であるみたいなのです。（もしかしたら存在するのか断定はできかねるが・・・）
> そこで一般に１～ｎの数字を円形に並べたとき、どの隣の２数の和が素数になるような配列を求めるプログラムを構成して頂きたいのですが、よろしくお願いします。


素数円 (prime circle)


LET N=7 !1, 3,5, 7,9, 11,13, 15,17 ,… ,4k±1はない
DIM F(N) !フラグ
MAT F=CON !1個ずつ
PUBLIC NUMERIC C !場合の数
LET C=0
DIM A(N) !環状の並び
MAT A=ZER
LET A(1)=1 !1の位置を固定する
LET F(1)=F(1)-1
CALL try(2,N,F, A)
PRINT C;"通り"
END
EXTERNAL SUB try(K,N,F(), A()) !バックトラック法で検索する
FOR i=2 TO N
   IF F(i)>0 THEN !未使用なら
      IF PrimeQ(A(K-1)+i)<>0 THEN !素数なら
         LET A(K)=i !仮に使用する
         IF K=N THEN
            IF PrimeQ(i+A(1))<>0 THEN
               MAT PRINT A; !結果を表示する
               LET C=C+1
            END IF
         ELSE
            LET F(i)=F(i)-1
            CALL try(K+1,N,F, A) !次へ
            LET F(i)=F(i)+1
         END IF
      END IF
   END IF
NEXT i
END SUB


!試行割算法（6k±1）

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 !３は素数
ELSE
   LET k=5
   DO WHILE k*k<=n !√nまで検証する
      IF MOD(n,k)=0 THEN !5,11,17,23,29,…
         EXIT FUNCTION
      ELSEIF MOD(n,k+2)=0 THEN !7,13,19,25,31,…
         EXIT FUNCTION
      END IF !+1,+3,+5は２の倍数（偶数）、+1,+4は３の倍数、+5は５の倍数
      LET k=k+6
   LOOP
   LET PrimeQ=1 !最後まで割り切れなければ、素数である
END IF
END FUNCTION

 		 

Re: プログラム依頼

 投稿者：GAI  投稿日：2016年 3月31日(木)13時22分59秒
  山中和義さんへのお返事です。

プログラムありがとうございます。
バックトラック法という名前をよく見ますがいまいちよくこれでうまく探すことができるのか不思議です。

> EXTERNAL SUB try(K,N,F(), A()) !バックトラック法で検索する

奇数では存在しなかったので安心しました。（でもどうしてだろう？）
偶数では必ず構成できることも不思議です。


話は変わりますが、1～nのカードが２枚ずつあるとき
3,1,2,1,3,2
と並べると
1と1のカードの間に1枚
2と2のカードの間に2枚
3と3のカードの間に3枚
というある意味バランスが整った並びができる。
4,1,3,1,2,4,3,2
も同様な配列となっている。
ところが
2,3,5,2,4,3,1,1,5,4 (１が反する)
1,4,1,5,3,2,4,2,3,5 (２が反する)
1,4,1,5,3,2,4,3,2,5 (３が反する)
のあと一歩までは近づくが完成には至らない。
1,6,1,5,2,4,2,3,6,5,4,3(2が反する)
1,6,1,3,5,2,4,3,2,6,5,4(6が反する)
も同様に後一歩
これ以降も存在しないかと思いきや
1,7,1,2,5,6,2,3,4,7,5,3,6,4
はバッチリ配列できた。

そこで1～5,1～6 では本当に不可能なのか、また可能ならnはどんなもので具体的並びはどうか？
が知りたくなりました。
これに対応できるプログラムを作って欲しいです。 		 

Re: プログラム依頼

 投稿者：山中和義  投稿日：2016年 3月31日(木)15時03分28秒
  > No.4023[元記事へ]

GAIさんへのお返事です。

> そこで1～5,1～6 では本当に不可能なのか、また可能ならnはどんなもので具体的並びはどうか？
> が知りたくなりました。
> これに対応できるプログラムを作って欲しいです。


考察
n≡0, 3 mod 4 の場合に限る。


1からnまでのn個の数の並べ方は、n!通り。
この数字の並びを左から見て、その順番に左詰めに並べていく。
例　n=4で、並びが1234の場合
　4×2=8個の枠○○○○○○○○について、
　1は、１○１○○○○○
　2は、１２１○２○○○
　3は、１２１３２○○３
　4は、並べられない
（終り）


その２
xが空きとすると、数字4は3通りの位置に置ける。
　12345678←位置
　4xxxx4xx
　x4xxxx4x
　xx4xxxx4



!問題 L(2,4)
!8個の数 1,1,2,2,3,3,…,4,4 をうまく一列に並べると、
!1≦n≦4を満たす全ての自然数nに対して、
!2つのnの間にはn個の数があるようにすることが出来ることを示してください。

LET t0=TIME
LET N=4
PUBLIC NUMERIC C !解の個数
LET C=0
DIM F(2*N) !並び
MAT F=ZER
CALL try(N, N,F)
IF C=0 THEN PRINT "解なし"
PRINT TIME-t0
END

EXTERNAL SUB try(P, N,F()) !バックトラック法で検索する
FOR i=1 TO 2*N-(P+1) !未使用の位置が候補である
   IF F(i)=0 AND F(i+(P+1))=0 THEN !組(i,i+(p+1))は条件を満たす
      LET F(i)=P !使用中
      LET F(i+(P+1))=P

      IF P=1 THEN !すべて並んだなら
         LET C=C+1
         PRINT "No.";C
         MAT PRINT F;
      ELSE
         CALL try(P-1, N,F) !次へ
      END IF

      LET F(i)=0 !元に戻す
      LET F(i+(P+1))=0
   END IF
NEXT i
END SUB

 		 

戻る