2021-12-22

電子計算機を使わないで発見された最大の素数 (2^148+1)/17（Ferrierの素数）

数学素数整数論アドベントカレンダー

日曜数学 Advent Calendar 2021 の17日目の記事です。

今日は

$\displaystyle N = \frac{2^{148}+1}{17} = 20988936657440586486151264256610222593863921 \tag{1}$

という数について考えたいと思います。

この数、桁数が 44桁もある巨大な数なのですが、なんと素数であることが分かっています。

1951年に素数であることが証明されたのですが、面白いことに

電子計算機を使わないで発見された最大の素数

という二つ名がつけられています。そう聞くとなかなか興味深く思えてきますよね！　一体どのようにして証明されたのでしょうか！？

今日は、この数が素数であることを判定する、Ferrier（以降、フェリアーと呼ぶことにします *1）による方法を紹介したいと思います。

「素数である」という事実は後で紹介するWikipediaにも書いています。しかいながら、素数であることを証明する方法は、インターネット上を探してもなかなか見つかりません。今回、色々頑張って参考になる本を見つけたので、その内容をベースに紹介したいと思います。

Prime Numbers and Computer Methods for Factorization (Progress in Mathematics)

作者:Riesel, Hans
Springer

Amazon

なお、フェリアーの方法にこだわらないのであれば、ミラーラビン法を使えばコンピュータを使って一瞬で素数判定できます。

たとえば、以下のサイトで "20988936657440586486151264256610222593863921" を判定してみてください。
tsujimotter.info

実際、このような結果が出て、素数であることがわかるでしょう。

なお、ミラーラビン法は厳密に言えば「確率的素数判定法」であり、上記の判定も（非常に低確率ですが）誤りである可能性があります。一方で、ミラーラビン法の前身である「ミラー法」であれば（一般化リーマン予想の仮定の下で）確定的に判定できます。このぐらいの桁数であれば、数秒もあれば判定できます。（実際にやってみました。）

ところで、ミラーラビン法の元となったミラー法は1976年に提案されていますので、フェリアーの1951年当時には存在しなかったことになります。

さらにいえば、コンピュータだったからこそ一瞬だったわけで、ミラーラビン法を手計算や機械式計算で行うのは至難の技かと思います。あまりおすすめはしませんが、興味がある方はやってみてください。

*1:Ferrierのカタカナ表記については、定番のものはなさそうに思えます。今回はHardy and wrightの本の表記を参考にしました：

数論入門 I (シュプリンガー数学クラシックス第)

作者:G.H.ハーディ,E.M.ライト
丸善出版

Amazon

2021-12-17

フィボナッチ数の逆数和がテータ関数を使って表せるという話

数学整数論

今日のテーマはフィボナッチ数です。

またかと思われるかもしれませんが、最近たしかにフィボナッチ数の話が多いですね。

今日の切り口は、フィボナッチ数の逆数和です。特に、奇数番目のフィボナッチ数の逆数和

$\newcommand{\HLNO}{\unicode[\sans-serif,STIXGeneral]{x306E}} \displaystyle \begin{align*} \sum_{n=0}^{\infty} \frac{1}{F_{2n+1}} &= \frac{1}{F_{1}} + \frac{1}{F_{3}} + \frac{1}{F_{5}} + \frac{1}{F_{7}} + \cdots \\ &= \frac{1}{1} + \frac{1}{2} + \frac{1}{5} + \frac{1}{13} + \cdots \end{align*} \tag{1}$

について考えたいと思います。

式 $(1)$ の和を100項ぐらい数値計算させてみると、だいたい次のような数値となります：

$\displaystyle \sum_{n=0}^{\infty} \frac{1}{F_{2n+1}} \fallingdotseq 1.8245151574 \tag{2}$

今日はこの和を、テータ関数を使って表すことができるというお話を紹介したいと思います。

単に関数の式変形ができる、という話にとどまらず、その導出にはヤコビの2平方和の定理が出てくるなど、整数論とも繋がりがあって大変おもしろいです。

よろしければ最後までお付き合いください。

2021-12-02

小数展開にフィボナッチ数列 etc. が出てくる分数（後編）

数学アドベントカレンダー循環小数

日曜数学 Advent Calendar 2021 の2日目の記事です。

昨日の記事の後編として、小数展開に色々な数列が登場するような分数を生み出していきたいと思います！

さてここで問題です！

以下の４つの分数は、それぞれどんな数列が出てくる分数でしょうか？

$\displaystyle \frac{10000}{9799}$
$\displaystyle \frac{1010000}{999899}$
$\displaystyle \frac{2999900}{999899}$
$\displaystyle \frac{10100}{970299}$

（答えは記事の中で紹介します。）

前編の記事をまだ読んでいない方は、前編の記事をぜひご覧になってください。
tsujimotter.hatenablog.com

前回に続いて、分数の小数展開には以下のページをご活用ください！
tsujimotter.info

2021-12-01

小数展開にフィボナッチ数列 etc. が出てくる分数（前編）

数学アドベントカレンダー循環小数

日曜数学 Advent Calendar 2021 の1日目の記事です。

アドベントカレンダーの季節がやってまいりました。今年も日曜数学アドベントカレンダーを立てまして、この記事はその1日目の記事となっています。
adventar.org

日曜数学アドベントカレンダーは、今年で 7年目になります。なかなか続いていますね。

まだまだ空きはありますので、よろしければご参加お待ちしています。みなさまの記事を楽しみにしています！

トップバッターのこの記事では

$\displaystyle \frac{100}{9899} \tag{1}$

という分数について考えてみましょう。

実際に計算して、小数展開を求めてみるとこうなります：

$\displaystyle \require{color} \frac{100}{9899} = {\color[rgb]{1.000000,0.000000,0.200000}0.01010203050813213455}90463\ldots \tag{2}$

小数部分を2桁ずつ区切ってみると

$\displaystyle {\color[rgb]{1.000000,0.000000,0.200000}0.\;01\;01\;02\;03\;05\;08\;13\;21\;34\;55}\;90\;46\;3\ldots$

となりますが、ここから

$\displaystyle {\color[rgb]{1.000000,0.000000,0.200000}0, \; 1, \;1, \;2, \;3, \;5, \;8, \;13, \;21, \;34, \;55}$

という数列が得られますね。

この数列、なんとフィボナッチ数列になっているのです！　面白いですよね！

いったいどういう仕組みでフィボナッチ数列が出てくるのでしょうか。今日はその理屈を解説したいと思います。

フィボナッチ数列以外にも、同様の仕組みで数列の値が小数展開に出てくる分数を作ることができます。これについても紹介したいと思います。（後編の記事で紹介します。）

それでは、最後までぜひご覧ください！

なお、今回の記事では、分数の小数展開を計算することが必要になります。電卓で計算する際は、桁数に限界があり不便です。

そこで以下のページで、小数展開を任意の計算精度で出せるようにしてみました！　自分で計算してみると楽しいので、よろしければご活用ください。
tsujimotter.info

2021-10-31

循環小数とアルティン予想

数学循環小数ゼータ関数

これまでtsujimotterのノートブックでは、循環小数についていろいろな話題を紹介してきました。今日はとっておきのトピックとしてアルティン予想という未解決問題について紹介したいと思います。

これまでの記事はこちらから見ることができます：
tsujimotter.hatenablog.com

このブログでは、これまでずっと「素数 $p$ の逆数 $1/p$ の循環節の長さ」について興味を持ってきました。

まずは、 $p \neq 2, 5$ なる素数 $p$ について、 $1/p$ の循環小数を計算してみましょう。例として $30$ 以下のものを計算してみます：

$\; 1/3 = 0.\overline{3}$ 　（長さ: 1）
$\; 1/7 = 0.\overline{142857}$ 　（長さ: 6）
$1/11 = 0.\overline{09}$ 　（長さ: 2）
$1/13 = 0.\overline{076923}$ 　（長さ: 6）
$1/17 = 0.\overline{0588235294117647}$ 　（長さ: 16）
$1/19 = 0.\overline{052631578947368421}$ 　（長さ: 18）
$1/23 = 0.\overline{0434782608695652173913}$ 　（長さ: 22）
$1/29 = 0.\overline{0344827586206896551724137931}$ 　（長さ: 28）