March 2016
<<February March April>>
There are two solutions for 15 digits: 182921919071841 and 655785969669834.
We found a solution for 18 digits (650700037578750084) and Mathias Schenker found one for 21 digits: 673774165549097456624.
Liubing Yu and Robert Gerbicz found larger solutions:
125631041500927357539
673774165549097456624
16719041449406813636569
61250745649972742370386904
67606700276236965651817526
90023320070600225470121747
90061407515524778881607747
1487765520677699458074768471
4403809479672994628231714138
6137500977894954428169516854
After we published the challenge, an OEIS entry was created (https://oeis.org/A269588). At the time we published this page, the larger solutions are still not there.
Here is Robert Gerbicz's explanation:
There is no more squarereversed number in the (10^15,10^30) interval, to get this it took me roughly 152 thread hours on a single Intel Core i3 processor.
I've used an O(10^(2*d/5)) algorithm (using O(10^(d/5)) memory), which is an improvement of the obvious O(10^(d/2)) algorithm, if we search all d digits squarereversed number. (d=n in the puzzle).
To reach a speed up by a factor of 10^k: let t=2*k-(d%2) suppose that N is a squarereversed number and h=N%(10^g), where g=(d-t)/2, note that here g=d/2-k+(d%2)/2.
N^2==h^2 mod 10^g, from this we know the first g digits of N. What is missing is the middle t digits of N.
If the t middle digits is x, then N==h+x*10^g mod 10^(t+g)
so (eq) N^2==h^2+2*10^g*(h*x) mod 10^(t+g), if t<=g is true.
let r=(h^2\10^g) mod 10^t. In N^2 in the t middle position's of N we see the reverse of x, thus using (eq):
rev0(x,t)==r+2*h*x mod 10^t, where rev0(z,l) is the reverse of z if z has l digits, and here leading zero is possible.
And that is what we'll use, for fixed x and fix h mod 10^t=N mod 10^t:
r==rev0(x,t)-2*h*x mod 10^t, so for r the solution is unique, calculate this r for each x=0,1,..,10^t-1.
Using this table we can get the good x values for each r (and in average we expect one good x value), with these middle digits we know all digits of N, check if it is a squarereversed number or not. The total additional computation cost is O(10^(2*t))=O(10^(4*k)), because for fixed (N mod 10^t) we spend O(10^t) to build the table and there are 10^t possibilities for (N mod 10^t). And we need O(10^t)=O(10^(2*k)) memory.
It is easy to see that the optimal k value is: k=(d+1)\10; actually used k=(d+3)\10 in my code.
Another small trick: N is not divisible by 10: otherwise N^2 is also divisible by 100, but then a1=0.
Furthermore in the above algorithm to make the table it is enough to know N mod ((10^t)/2) since rev0(x,t)==r+2*h*x mod 10^t so we would build the same table for h and h+(10^t)/2.
Update 8/6: Dieter Beckerle used Robert Gerbicz's method and found that there is no 31 digits squarereversed number, and exactly one 32 digits number:
42438303108538316396992097393368 ^ 2 = 1801009570732172928511403961864086339379029969361383580130383424
by choosing g=13, k=3, t=6: N = a*10^19 + x*10^13 + h (a and h has 13 digits, x has 6 digits)
a = rev((h^2)%(10^13),13)
x (6 digits) is the solution of the equation
rev0(x,6) == r + 2*h*x mod 10^6
with r = (h^2\10^13) mod 10^6, using tables (there are r-h-combinations with 1000 solutions (values of x)).