メルセンヌ数

書いた！

かなり読み物的な記事にはなってしまった。

リュカテストは任意精度整数が扱えることのご利益が分かりやすく、かつ実装が難しくない例として非常にちょうど良い。階乗計算やフィボナッチ数(それぞれ $21!$ , $F_{94}$ でu64からオーバーフロー)を計算するのはそれほど面白くはない。素因数分解や楕円曲線は実装が難しい。その点、プリミティブ型の値であるi128::MAXが素数であることを確かめるための効率の良い方法を実装するのに任意精度整数が必要になる、というのは自明ではなくて面白いと思う。

e

ツイッターで見たやつ

I think 18 trillion digit is an understatement
e-(1+1/n)^n = e/(2n) + O(n^-2)
since n = 3^2^85 ≈ 10^(1.846×10^25), this error is 10^(-1.846×10^25)
in other words, first 18 septillion digits should be correct
— otter_us (@OtterSou) September 30, 2021

おもしろ～～

このリプライの近似式は、 $f(x):=(1+x)^{1/x}$ をえいっとテイラー展開して

\frac{1}{e}f(x) = 1-\frac{x}{2}+\frac{11 x^2}{24}-\frac{7 x^3}{16}+\frac{2447 x^4}{5760}-\frac{959x^5}{2304}\cdots

から得られる。

さて、もっと先まで係数を計算させると（Maximaを利用）、右辺の係数は第10項で

\frac{29128857391}{73574645760} \simeq 0.3959089043529769,

第50項で

\frac{348039919973656042150801335523691824075978776245519944761812565714466734909742722329847811}{929039043468046536662197520717136390714658188483653224781582111999767093444608000000000000} \simeq 0.3746235665989279

という怪しげな値になる。たぶん、

e^{-1} \simeq 0.3678794411714423

に漸近する。というか、 $f(x)$ のテイラー展開の係数が $1$ に近付く。もっと先まで計算させるには、

\frac{1}{e}f(x) = \exp\left(\frac{-x}{2}\right)\exp\left(\frac{x^2}{3}\right)\exp\left(\frac{-x^3}{4}\right)\exp\left(\frac{x^4}{5}\right)\cdots

か、 $f(x)$ の対数微分で漸化式を得るかすれば係数は求められるはず。Maximaのtaylorだとこれ以上やらせるのはきつい。せっかくなのでRustを使って漸近する様子を見てみたい。

しかしテイラー展開の係数の漸近形はどうすれば求められるんだろう？

メルセンヌ・ツイスタ

Mersenne Twister: A random number generator (since 1997/10)

理解したい……言うだけならタダ。

その前に二次篩法でメルセンヌ数の素因数分解しないと。中核で疎行列を使っているので、そのあたりも調べることになる。