Editing AutomorphicNumbers
You are currently browsing as guest..
To change this, fill in the following fields:
Username
Password
Click here to reset your password
Who can read this page?
The World
Members
Council
Admin
You have been granted an edit lock on this page
until Fri Mar 29 05:35:25 2024.
Press
to finish editing.
Who can edit this page?
World editing disabled
Members
Council
Admin
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.