A an n-digit number is said to be curious if the last n digits of its square are the same as the original number. For example, 252 = 625 and 762 = 5776. (Curious numbers are also known as automorphic numbers.)
There are bigger curious numbers, such as 212890625 and 787109376:
2128906252 = 45322418212890625
and
7871093762 = 619541169787109376.
And if the square of x has the same last n digits as x, so does the cube of x and all higher powers.
It turns out that for each n > 1, there are two curious numbers of length n.
Always two there are; no more, no less. — Yoda
There’s even a formula for the two solutions. The first is the remainder when 5 to the power 2n is divided by 10n and the second is 10n + 1 minus the first.
Here’s a little Python code to show that the first several solutions really are solutions.
for i in range(2, 20):
a = 5**(2**i) % 10**i
b = 10**i - a + 1
print((a**2 - a)%10**i, (b**2 - b)%10**i)
Related: Applied number theory
Hmm. Just on a lark, I implemented this in Perl 6. Only instead of checking the results work like you do, I actually printed them out. Two things jumped out at me:
1) I initially assumed (without really thinking about it) that the n = 1 case doesn’t work because there is only one solution. Actually (of course!) it doesn’t work because there are three: the two that fit your formula (5 and 6) and the bonus solution 1.
2) A number of the generated solutions only have n digits if you prepend leading zeros. So 625 squared is 390625; it is the “a” solution for both n = 3 and n = 4. On the other hand, 9376 squared is 87909376, which is the “b” solution for n = 4 and n = 5.
This is really a statement about the 10-adics, right? There are exactly two solutions to x^2=x in the 10-adics (besides the trivial solutions 0, 1) and these things are the finite final segments of them.
for really big numbers (>20 digits, i.e. >2**64) it’s better to use pow(b,p,m).
for i in range(2, 45):
a = pow( 5, 2**i, 10**i ) # == 5**(2**i) % 10**i
b = 10**i – a + 1
assert (a**2 – a)%10**i == 0 and (b**2 – b)%10**i == 0
print(“%2d”%i,”%45d”%a,”%45d”%b)
Noticed what Sol said: In some cases one of the “n digit solutions” is > 9*10^(n-1) +1 so the other solution has n-1 digits. So:
1 digit: 1, 5, 6
2 digits: 25, 76
3 digits: 625, 376
4 digits: 9376 (only one: 10001-9376 = 625)
5 digits: 90625 (only one: 100001-90625 = 9376)
6 digits: 890625, 109376
and so on.
@Chris Eagle: yes, exactly. I actually wrote a nine-post series about this on my blog a while back: here is the last post in the series, which has links to all the previous ones. It features both curious numbers along with a proof of the “Yoda theorem”.
Does the Python snippet work for others? Here’s what I get:
Hi, it works in py3.x
[i for i in range(2000000) if i == int(str(i**2)[-len(str(i)):])]
There aren’t always 2, for example if n = 4; though, yes, there are always “potentially” two.
Thanks for all the interesting topics!
Maslanka, I don’t understand your example. When n = 4, I get 625 and 9376. Am I missing something?
In response to your query to Maslanka:
From your original post:
“It turns out that for each n > 1, there are two curious numbers of length n.”
625 does not have a length of 4, it has a length of 3.
The same happens with n = 5: your formulae would give 90625 & 9376, but only one of them has len=5. The same happens at n=12, and again at n=13.
Dear John,
I hope all is going well for you.
You said that there are infinitely automorphic (curious) numbers. Do you have a simple proof?
I have worked 12 years on magic squares: carres-magiques.com
Now, I work on a new website: more than 70 texts on different mathematical subjects.
Your proof will be in my Text no. 57. In that one, I give a nice proof of the result: there exist only 89 narcissic numbers.
Great thanks,
Claude Bégin
P.S. Excuse my English, not so good!!