素数出現関数を求めて

 投稿者：GAI  投稿日：2012年12月29日(土)17時20分3秒
  PARI/GPという計算ソフトで素数構成関数ができないか挑戦してみました。
まず素数の部分を指定できるように
F(j)=(j-1)!^2%j             !%は余りを出す演算です。（実質０か１が出力されます。）
を定義しました。

次に、整数ｍまでに存在している素数の個数を調べます。
G(m)=sum(j=1,m,F(j))

T(m,n)=floor(((n+1)/(G(m)+1))^(1/(n+1))) 　!0で割り算が起こらないように調整している。
P(n)=1+sum(m=1,2^n+1,T(m,n))               !上でずらした分2^n+1の処理にしている。

でn番目の素数を出す関数P(n)を定義します。

for(n=1,20,print(n,";",P(n-1)))   !ｎとの整合を起こすために、P(n-1)の表示にしている。

出力結果
1;2
2;3
3;5
4;7
5;11
6;13
7;17
8;19
9;23
10;29
11;31
12;37
・・・
・・・

と出力していく。
ただし１１番目以降は2^n+1の処理に時間が膨大に膨れていく。
これを組み合わせると素数を求める一つの式にできるような気がしますが・・・


この流れをBASICに書き直して頂けませんか。





 		 

Re: 素数出現関数を求めて

 投稿者：山中和義  投稿日：2012年12月30日(日)13時52分57秒
  > No.2794[元記事へ]

GAIさんへのお返事です。

> PARI/GPという計算ソフトで素数構成関数ができないか挑戦してみました。

> この流れをBASICに書き直して頂けませんか。

BASICで記述しても非実用的ですね。



FOR N=1 TO 20
   PRINT N; P(N)
NEXT N
END

EXTERNAL FUNCTION F(J) !素数判定　1:素数、0:素数でない　→PrimeQ(j)
LET S=1 !Wilsonの定理「pが素数⇔(p-1)! ≡-1 (mod p)」より、0,1を返す
FOR i=2 TO J-1 !(j-1)!
   LET S=MOD(S*i,J)
   IF S=0 THEN EXIT FOR
NEXT i
LET F=MOD(S*S,J) !(j-1)!^2 mod j
END FUNCTION

EXTERNAL FUNCTION G(M) !m以下の素数の数　→PrimePi(m)
LET S=0
IF M>=2 THEN LET S=1 !2は素数
FOR J=3 TO M STEP 2 !奇数を対象とする
   LET S=S+F(J)
NEXT J
LET G=S !Σ[j=2,m]PrimeQ(j)
END FUNCTION

EXTERNAL FUNCTION T(M,N) !xが1より大きいときxの正のx乗根は1～2の間の数になる
LET T=INT( (N/(G(M)+1))^(1/N) )
END FUNCTION

EXTERNAL FUNCTION P(N) !n番目の素数　→Prime(n)
LET S=0
FOR M=1 TO 2^N
   LET S=S+T(M,N)
NEXT M
LET P=S+1
END FUNCTION

 		 

Re: 素数出現関数を求めて

 投稿者：GAI  投稿日：2012年12月31日(月)01時29分19秒
  > No.2824[元記事へ]

山中和義さんへのお返事です。

>

の記事を参考にプログラムを変更し

P(n)=1+sum(m=1,2*floor(n*log(n)+1),(1-floor((sum(j=1,m,(j-1)!^2%j)/n))))

なる一つの式で構成してみました。（PARIでのプログラム）
（指数関数部分が対数関数処理でいけるものを選びました。）

n=1～100は軽く表示してくれます。
またn=150でも１分位待っていますとP(150)=863
の素数を返してきました。
前のに比べたら格段の進歩になりました。
 		 

Re: 素数出現関数を求めて

 投稿者：MyTrade  投稿日：2012年12月31日(月)09時17分57秒
  > No.2794[元記事へ]

GAIさんへのお返事です。

＊山中和義さんのプログラムの関数P(N)の部分を改善してみました。

EXTERNAL FUNCTION P(N) !n番目の素数　→Prime(n)
LET S=0
FOR M=1 TO 2^N
   LET tt=T(M,N)
   IF tt=0 THEN EXIT FOR !途中打ち切り
   LET S=S+tt
NEXT M
LET P=S+1
END FUNCTION

100番目までのすべての素数を出力するのに約3分です。
P(150)の計算は約30秒でした。


＊関数P(N)は次のように定義することも可能です。

EXTERNAL FUNCTION P(N) !n番目の素数　→Prime(n)
LET ss=1
LET M=0
DO
   LET M=M+1
   LET ss=ss+T(M,N)
LOOP UNTIL M=ss
LET P=ss
END FUNCTION
 		 

戻る