Edit made on March 03, 2009 by derekcouzens at 19:18:46
Deleted text in red /
Inserted text in green
WW
HEADERS_END
Numbers that end in themselves when squared are known as automorphic numbers. Two examples are 25^2 = 625 and 376^2 = 141376.
Numbers that end in themselves when squared are known as automorphic numbers. Two examples are EQN:25^2=625 and EQN:376^2=141376.
Automorphic numbers always arise in pairs that sum to numbers of the
form EQN: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 EQN:a_n ) is a multiple of EQN:5^n and congruent to 1 modulo EQN:2^n ; the second is a multiple of EQN:2^n and congruent to 1 modulo EQN:5^n . These numbers always exist and are unique modulo EQN:10^n , by the Chinese remainder theorem.
You can find EQN:a_n simply but inefficiently as follows. Start with EQN:a_1=5. Then, for all /n,/ EQN:a_{n+1} is the last EQN:n+1 digits of EQN:{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 EQN:a_n and want EQN:a_{n+1}. Clearly EQN:a_{n+1}=a_n+10^nr for some r; that is, EQN:a_{n+1} differs from EQN:a_n just by having some digit stuck on at the left. So, what's /r/ ? Well, we have EQN:10^nr\equiv~-a_n\pmod{5^{n+1}} and EQN:10^nr\equiv~1-a_n\pmod{2^{n+1}}, and so EQN:2^nr\equiv~-a_n/5^n\pmod{5} and EQN:5^nr\equiv~(1-a_n)/2^n\pmod{2}. (Those right-hand sides are guaranteed to be integers by the definition of EQN:a_n. )
So if, as we construct the table above, we keep track of EQN:a_n/5^n and EQN:(1-a_n)/2^n as well as EQN:a_n and EQN:b_n, then all we need to know is the reciprocal of EQN:2^n modulo 5 (this is a repeating sequence: 3,4,2,1,3,4,2,1,...) and the reciprocal of EQN:5^n modulo 2 (this is always 1, of course). So, here's the final algorithm. Write EQN:a_n=5^nc_n and EQN:b_n=2^nd_n, and let EQN:v_n be the repeating sequence of reciprocals. Then
* EQN:a_1=5, EQN:b_1=6, EQN:c_1=1, EQN:d_1=-2.
* Let /r/ be the (unique) digit that's congruent mod 5 to EQN:-v_nc_n and congruent mod 2 to EQN:d_n. Then
** EQN:a_{n+1}=a_n+10^nr; EQN:b_{n+1}=10^{n+1}+1-a_n; EQN:c_{n+1}=(c_n+2^nr)/5; EQN:d_{n+1}=(d_n-5^nr)/2.
Example: for EQN:n=5 we have /a,b,c,d,v/ = 90625,9376,29,-2832,3; so /r/ equals EQN:-3.29\equiv-87\equiv3 mod 5 and EQN:-2832\equiv0 mod 2; the only digit that works is 8.