メインメニュー
PR
facebook
別フォーラムへ

素数に関する話題

投稿ツリー


このトピックの投稿一覧へ

Allegro

なし 素数に関する話題

msg# 1
depth:
0
前の投稿 - 次の投稿 | 親投稿 - 子投稿.1 .2 .3 .4 .5 .6 | 投稿日時 2014/1/19 12:59
Allegro  半人前   投稿数: 25
//**********************************
// (命題)
//
// nを素数とする。このとき、nが小さい方から何番目の素数であるかは
// (n以下の素数表がなくても)下記関数を用いて計算できる(効率は極めて悪いが)。
//
// いんでっくす(n)≡1+Σ(a=2..n-1)[Π(b=2..a-1){1-1/b・Σ(c=1..b)(ζ<b>^(c*n))}]...[A]
//
// ただし、ζ<b>≡cos(2π/b)+isin(2π/b)とする。
//
// また、 Σ(a=b..c)d(a) は、d(b)+d(b+1)+...+d(c)と言う意味で、
// 同様に、Π(a=b..c)d(a) は、d(b)*d(b+1)*...*d(c)と言う意味で
// それぞれ表現しているものとする。
//**********************************
ということを証明しようと思っています。

ごく簡単に説明すると、

1)自然数を自然数で割った余りの表を考えました。

除数 y 1 2 3 4 5 6 7 8 9 10 ...
被除数 x
1   0 1 1 1 1 1 1 1 1 1 ...
2   0 0 2 2 2 2 2 2 2 2 ...
3   0 1 0 3 3 3 3 3 3 3 ...
4   0 0 1 0 4 4 4 4 4 4 ...
5   0 1 2 1 0 5 5 5 5 5 ...
6   0 0 0 2 1 0 6 6 6 6 ...
7  0 1 1 3 2 1 0 7 7 7 ...
8  0 0 2 0 3 2 1 0 8 8 ...
9  0 1 0 1 4 3 2 1 0 9 ...
10  0 0 1 2 0 4 3 2 1 0 ...
...
そこで、余りの周期性に着目し、割り切れるかどうかの判定関数を考えます。

判定関数として、はんてい(x,y)≡1/y*{Σ(c=1,,y)(ζ<y>^(c*x))}と
表現する方法にたどり着きました。

たとえば、自然数4なら、

はんてい(4,1)=1/1*{ζ<1>^(1*4)} =1
はんてい(4,2)=1/2*{ζ<2>^(1*4)+ζ<2>^(2*4)}=1
はんてい(4,3)=1/3*{ζ<3>^(1*4)+ζ<3>^(2*4)+ζ<3>^(3*4)}=0
はんてい(4,4)=1/4*{ζ<4>^(1*4)+ζ<4>^(2*4)+ζ<4>^(3*4)+ζ<4>^(4*4)}=1

で、4は1,2,4で割り切れ、3で割り切れません。

素数5の場合は、

はんてい(5,1)=1/1*{ζ<1>^(1*5)} =1
はんてい(5,2)=1/2*{ζ<2>^(1*5)+ζ<2>^(2*5)}=0
はんてい(5,3)=1/3*{ζ<3>^(1*5)+ζ<3>^(2*5)+ζ<3>^(3*5)}=0
はんてい(5,4)=1/4*{ζ<4>^(1*5)+ζ<4>^(2*5)+ζ<4>^(3*5)+ζ<4>^(4*5)}=0
はんてい(5,5)=1/5*{ζ<5>^(1*5)+ζ<5>^(2*5)+ζ<5>^(3*5)+ζ<5>^(4*5)+ζ<5>^(5*5)}=1

で、5は1,5のみで割り切れます。

はんてい(6,1)=1/1*{ζ<1>^(1*6)} =1
はんてい(6,2)=1/2*{ζ<2>^(1*6)+ζ<2>^(2*6)}=1
はんてい(6,3)=1/3*{ζ<3>^(1*6)+ζ<3>^(2*6)+ζ<3>^(3*6)}=1
はんてい(6,4)=1/4*{ζ<4>^(1*6)+ζ<4>^(2*6)+ζ<4>^(3*6)+ζ<4>^(4*6)}=0
はんてい(6,5)=1/5*{ζ<5>^(1*6)+ζ<5>^(2*6)+ζ<5>^(3*6)+ζ<5>^(4*6)+ζ<5>^(5*6)}=0
はんてい(6,6)=1/6*{ζ<6>^(1*6)+ζ<6>^(2*6)+ζ<6>^(3*6)+ζ<6>^(4*6)+ζ<6>^(5*6)+ζ<6>^(6*6)}=1

この性質を利用して式を工夫してやれば、[A]式が構築できる、というわけです。
で、証明したいことは、

あ)はんてい(x,y)が本当に、x%y=0なら1,x%y<>0なら0を常に満たしているか?
い)[A]式は妥当か

の二点です。

ちなみに、プログラムで検証した限りでは、[A]式は正しく作用するようです。

※最終目的は、いんでっくす(n)から逆算してnを求めることです。

--
//*********************************
★✩Allegro@長野県塩尻市✩★
ヾ(@⌒ー⌒@)ノ
♡西脇綾香(Perfumeあ~ちゃん)大好き
//*********************************

投票数:0 平均点:0.00
返信する

この投稿に返信する

題名
ゲスト名
投稿本文

  条件検索へ



ログイン

ユーザー名:


パスワード:





パスワード紛失  |新規登録
PR
twitter
Created by: twitter website widget