非自明１の平方根の計算

10 adic number の世界では非自明な1の平方根が存在します。その近似計算法についてまとめます。

方法1

１の平方根と2乗しても変わらない数によれば \[ \sqrt{1} = \lim_{n\to \infty} \frac{5^n-2^n}{5^n+2^n} \] によって求めることができます。ここで注意したいのは右辺の割り算はmodの世界の割り算として行わなければならない点です。 Maximaでは mod n の世界のaの逆数は

inv_mod(a,n)

によって求めることができます。

N:10$ /*10桁求める*/
M:10^N$ 
a(n):=mod(5^n-2^n,M)$
b(n):=inv_mod(5^n+2^n,M)$
c(n):=mod(a(i)*b(i),M)$
for i thru N+2 do print(c(i))$

実行結果.

実行結果から、収束していく様子が見て取れます。

最後の行を取り出して、これが本当に１の平方根の近似値になっているか、次のように検算してみます。

a:6425781249$ a^2;

実行結果.

41290664660000000001

確かに、10進数的に1に近い数になっていることが確認できます。

方法2

\[ \lim_{n \to \infty} 5^{2^n} = \frac{1+\sqrt{1}}{2} \] を利用します。これを$\sqrt{1}$についてとくと \[ \sqrt{1} = 2\lim_{n \to \infty} 5^{2^n} -1 \] が得られます。

単純にmodだけを使用すると、すぐにオーバーフローを起こしてしまいますので指数に特化した関数
power_mod を利用します。

power_mod(a,b,n) は a^b mod n を計算します。

N:10$
c(n):=mod(2*power_mod(5,2^i,10^N)-1,10^N)$
for i thru N+2 do print(c(i))$

実行結果.

外側のmodにあまり意味はありません。これを外しても計算できますが、１桁ほど信用できない桁が入る可能性があります。