Automorphic Numbers |
|
Automorphic numbers always arise in pairs that sum to numbers of the form $10^n+1.$ The first five pairs (in some cases including numbers with leading zeroes) are:
1st | 2nd | sum |
5 | 6 | 11 |
25 | 76 | 101 |
625 | 376 | 1001 |
0625 | 9376 | 10001 |
90625 | 09376 | 100001 |
890625 | 109376 | 1000001 |
The first number in each pair (call it $a_n$ ) is a multiple of $5^n$ and congruent to 1 modulo $2^n$ ; the second is a multiple of $2^n$ and congruent to 1 modulo $5^n$ . These numbers always exist and are unique modulo $10^n$ , by the Chinese remainder theorem.
You can find $a_n$ simply but inefficiently as follows. Start with $a_1=5.$ Then, for all n, $a_{n+1}$ is the last $n+1$ digits of ${a_n}^2.$ If you want to avoid having to deal with "double-length" numbers, here's one way to do it:
Suppose we know $a_n$ and want $a_{n+1}.$ Clearly $a_{n+1}=a_n+10^nr$ for some r; that is, $a_{n+1}$ differs from $a_n$ just by having some digit stuck on at the left. So, what's r ? Well, we have $10^nr\equiv~-a_n\pmod{5^{n+1}}$ and $10^nr\equiv~1-a_n\pmod{2^{n+1}},$ and so $2^nr\equiv~-a_n/5^n\pmod{5}$ and $5^nr\equiv~(1-a_n)/2^n\pmod{2}.$ (Those right-hand sides are guaranteed to be integers by the definition of $a_n.$ )
So if, as we construct the table above, we keep track of $a_n/5^n$ and $(1-a_n)/2^n$ as well as $a_n$ and $b_n,$ then all we need to know is the reciprocal of $2^n$ modulo 5 (this is a repeating sequence: 3,4,2,1,3,4,2,1,...) and the reciprocal of $5^n$ modulo 2 (this is always 1, of course). So, here's the final algorithm. Write $a_n=5^nc_n$ and $b_n=2^nd_n,$ and let $v_n$ be the repeating sequence of reciprocals. Then