もう一人のY君

主にiPhoneのショートカットアプリのレシピやTipsなどを書いています. たまに数学の記事も書きます.

もう一人のY君 MENU  MENU

【数表】10000以下の素数の原始根一覧

 

 

 今回は久しぶりの数学の話です.

 

 

 

スポンサーリンク

 


 

 

過去記事

blog.thetheorier.com

 8年ほど前に500以下の素数については紹介しました.

 原始根が何なのかの説明は過去記事を参照してください.

 

 ただ素数が大きくなると当然原始根の数も(単調増加ではないですが)増えていきます.

 

 例えば素数9887の原始根は4942個もありますが、その次に大きい素数9901の原始根は一気に減って2400個です(素数pの原始根はφ(p-1)個).

 

 そのためひとつの記事に書こうとしたら2万文字3万文字ではとても足りません.

 なので今回はGitHubに頼ることにしました.

 

 

原始根一覧のリンク

github.com

 原始根の一覧を参照するにはこちらのリポジトリにアクセスします.

 

 

 "list"と"root.json"の2つ用意しています.

 "list"は元々json形式で書いたものをテキスト形式でアップロードしたもの.

 "root.json"はjsonファイルとしてアップロードしたものです.

 

 サイズが大きいのでどちらかで見やすい方があれば…と思ったんですが結果的にはどちらも重かったので好きな方を選んでください.

 

 今回はroot.jsonを選ぶことにします.

 

 

 上で書いた通り9.78MBとかなり大きいためその場で参照することができません.

 "Sorry about that, but we can't show files that are this big right now."の上にある"View raw"をタップするか(画像①)、右にある三点アイコンをタップし"View"をタップする(画像②)ことでコードを参照できます.

 

 

 画像の通り、素数をキーとし、その原始根は配列として構成されています.

 

 端末によっては開くだけで多少時間がかかります.

 

 下までスクロールするのも大変ですがちゃんと9973まであります.

 

 

参考:値を取り出す

 折角なのでiPhoneのショートカットアプリで値を取り出してみます.

 

 

 root.jsonの方を辞書として取り込み、希望のキーの値を取り出します.

 

 レシピ次第でちゃんと処理はしてくれますが、この程度のレシピですら2分以上かかるポンコツぶりなのでショートカットで直接使うのは無理ですね.

 

 

 本当は原始根を求めること自体をショートカットで組みたかったんですが、ショートカットは膨大な計算が苦手なので諦めました.

 

 今回の計算はGoogleスプレッドシートを使用しています、あんまり褒められたやり方ではないですが.

 素数pの原始根がひとつ(gとでもします)見つかれば、あとはp-1と互いに素な自然数aについてg^aもまたpの原始根であることを利用すれば芋づる式に求められます.

 原始根かどうかはgp-1に対応する、つまりg^e\equiv 1\pmod pとなる最も小さな正整数がeであればよいので、p-1乗までの結果が1と合同である個数をカウントすれば十分です.