New Scientist magazine's Enigma #49 problem can be solved with a bit of number theory. Generalising the problem to finding a number whose square has the same last N digits as itself:
z2 = z mod 10N → z(z-1) = 0 mod 10N. One factor of z(z-1) is odd, the other even. The even factor is a multiple of 2N.
For a solution other than 0 or 1, the odd factor of z(z-1) must be a multiple of 5N (if the even factor is a multiple of 5 it is a multiple of 10, so the odd factor is congruent to 1 or 9 mod 10 and therefore not a multiple of 5, so the even factor is a multiple of 10N).
So the solution is one of
a) z=2Nx, z-1=5Ny
b) z-1=2Nx, z=5Ny
Solutions to the Diophantine equation 2Nx+ 5Ny=1 produce the solutions
a) z=2N(x mod 5N)
b) z=5N(y mod 2N)
So, some Python code. Function egcd is a standard recursive implementation of the Extended Euclidean Algorithm to find solutions to a linear Diophantine equation (and the gcd as a by-product).
def egcd(a,b):
if b == 0:
return [1,0,a]
else:
x,y,g = egcd(b, a%b)
return [y, x - (a//b)*y, g]
for N in range(1,40):
x,y,g = egcd(5**N, 2**N)
print "N =",N, sorted([(x%2**N)*5**N, (y%5**N)*2**N])
There is another way to solve this, again using a recursive approach.
ReplyDeleteIf we use w = (3 n^2 - 2 n^3),Mod[10^2k]
then starting with n = 25 or 76 ( those are the only 2 automorphic numbers, and k = 1 and on each iteration let n = w and increment k by 1 will generate an infinite series of numbers. The following MMA program will generate the first 10 numbers.
k=1;n=25;
Do[w=Mod[3n^2-2n^3,10^(2k)];
Print[w," ",w^2];k++;n=w,{q,1,10}]
change the n = 25 to 76 to get the other set.
At the 50th iteration there are 100 and 200 digits in the answers,
incidentally I submitted this as a problem on the contest centre in 2012.
Paul.