Ponder This Challenge - March 2016 - Squareversed numbers

Ponder This Challenge:

This month's challenge is from Yan-Wu He (thanks!)
For a non-zero number (in list) (a1,a2,..,an), its square is (..., an,..,a2,a1),
Let's call the number N "squareversed" if its square ends with the reverse of N.
For example, N=69714 is "squareversed", since its square is 4860041796 which ends with 41796 (the reverse of N).
Find a 15 digits squarereversed number.
Bonus: Find a larger squarereversed number.

Solution

• Click here to view the solution

  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)).

Solvers

• **Robert Gerbicz (29/02/2016 12:00 PM IDT)
• **Arthur Vause (29/02/2016 01:59 PM IDT)
• *Armin Krauss (29/02/2016 02:19 PM IDT)
• *Aviv Nisgav (29/02/2016 04:39 PM IDT)
• Oleg Vlasii (29/02/2016 05:32 PM IDT)
• Daniel Bitin (29/02/2016 05:54 PM IDT)
• *Vladimir Sedach (29/02/2016 05:57 PM IDT)
• Hao Zheng (29/02/2016 06:24 PM IDT)
• **Mathias Schenker (29/02/2016 06:31 PM IDT)
• *Joseph DeVincentis (29/02/2016 07:51 PM IDT)
• **Lorenz Reichel (29/02/2016 10:57 PM IDT)
• **Motty Porat (29/02/2016 11:11 PM IDT)
• *Paolo Farinelli (29/02/2016 11:58 PM IDT)
• Uoti Urpala (01/03/2016 01:10 AM IDT)
• Radu-Alexandru Todor (01/03/2016 01:55 AM IDT)
• **Jesse Rearick (01/03/2016 02:03 AM IDT)
• Franciraldo Cavalcante (01/03/2016 03:04 AM IDT)
• **David F.H. Dunkley (01/03/2016 03:07 AM IDT)
• Victor Chang (01/03/2016 05:34 AM IDT)
• Kang Jin Cho (01/03/2016 07:24 AM IDT)
• Leo Broukhis (01/03/2016 10:56 AM IDT)
• *Sergey Koposov (01/03/2016 01:00 PM IDT)
• *Emir Haleva (01/03/2016 01:59 PM IDT)
• **Harald Bögeholz (01/03/2016 04:03 PM IDT)
• Alex Fleischer (01/03/2016 04:15 PM IDT)
• Guang-Zhong Sun (01/03/2016 05:45 PM IDT)
• **Dieter Beckerle (01/03/2016 08:53 PM IDT)
• *Jan van Delden (01/03/2016 09:10 PM IDT)
• *Nicolas Bitouze (01/03/2016 09:58 PM IDT)
• *Boris Hartmann (01/03/2016 11:32 PM IDT)
• **Justin C. Archer (02/03/2016 02:15 AM IDT)
• *Benjamin Lui (02/03/2016 03:23 AM IDT)
• Minxi Jiang (02/03/2016 05:17 AM IDT)
• Tamir Ganor & Shouky Dan (02/03/2016 09:35 AM IDT)
• Chris Shannon (02/03/2016 10:23 AM IDT)
• **Ariel Ish-Shalom (02/03/2016 04:41 PM IDT)
• *Rogerio Ponce da Silva (02/03/2016 05:34 PM IDT)
• **Liubing Yu (02/03/2016 05:38 PM IDT)
• *Lawrence Au (02/03/2016 08:28 PM IDT)
• Reiner Martin (03/03/2016 12:24 AM IDT)
• Cody Pfau (03/03/2016 12:42 AM IDT)
• Alan Murray (03/03/2016 03:10 AM IDT)
• **Amos Guler (03/03/2016 08:34 AM IDT)
• Roberto Tauraso (03/03/2016 02:57 PM IDT)
• *Tomáš Jurík (03/03/2016 03:29 PM IDT)
• **Franciraldo Cavalcante (03/03/2016 05:33 PM IDT)
• *José Eduardo Gaboardi de Carvalho (03/03/2016 06:11 PM IDT)
• Clive Tong (03/03/2016 09:56 PM IDT)
• *Kipp Johnson (03/03/2016 11:16 PM IDT)
• *Bruce Norskog (04/03/2016 03:59 AM IDT)
• *Hamidreza Bidar (04/03/2016 05:37 PM IDT)
• *Alain Stephan (04/03/2016 06:12 PM IDT)
• **Michael Rosola (04/03/2016 07:43 PM IDT)
• Stéphane Higueret (05/03/2016 12:37 AM IDT)
• **David Greer (05/03/2016 12:38 AM IDT)
• **Gary M. Gerken (05/03/2016 10:19 AM IDT)
• **Todd Will (06/03/2016 01:11 AM IDT)
• *Chad Barb (06/03/2016 02:28 AM IDT)
• Shirish Chinchalkar (06/03/2016 04:33 AM IDT)
• *Peter Gerritson (06/03/2016 10:55 AM IDT)
• Evert van Dijken (06/03/2016 04:46 PM IDT)
• **Andrea Silva (06/03/2016 07:35 PM IDT)
• *Yoav Kaempfer (07/03/2016 12:58 AM IDT)
• Taylor Firman (08/03/2016 01:45 AM IDT)
• **Rudy Cortembert (08/03/2016 04:23 PM IDT)
• **Karim Alaoui (08/03/2016 09:58 AM IDT)
• Hyun Min Victoria Woo (08/03/2016 11:09 PM IDT)
• *Erik Wünstel (09/03/2016 09:15 AM IDT)
• Christian Pfaffenzeller (09/03/2016 04:25 PM IDT)
• Zhizhong Zhou (10/03/2016 07:22 AM IDT)
• **Sami Casanova (10/03/2016 04:33 PM IDT)
• **Andreas Stiller (10/03/2016 03:15 PM IDT)
• **Aharon Malachi (10/03/2016 09:21 PM IDT)
• **Yingtao Tian (11/03/2016 12:31 AM IDT)
• **Raymond Lo (11/03/2016 03:39 AM IDT)
• **Stefano Leucci (11/03/2016 02:27 PM IDT)
• **Francis Golding (11/03/2016 07:34 PM IDT)
• **Yury X Volvovskiy (11/03/2016 11:05 PM IDT)
• *J. Eric Ivancich (12/03/2016 07:10 AM IDT)
• David Stevens (12/03/2016 02:17 PM IDT)
• **Emilio Del Tessandoro (12/03/2016 09:37 PM IDT)
• **Jimmy Waters (13/03/2016 01:47 AM IDT)
• *Matt Falk (13/03/2016 08:07 AM IDT)
• **Raymond Jackson (14/03/2016 11:51 AM IDT)
• Zhou Ding Wen (14/03/2016 04:01 PM IDT)
• **Adrian Orzepowski (14/03/2016 08:25 PM IDT)
• Bryce Fore (16/03/2016 09:46 AM IDT)
• **Koszó Norbert (16/03/2016 02:15 PM IDT)
• **Ram Shanker (17/03/2016 03:49 AM IDT)
• *Chenzi Zhang (17/03/2016 08:32 AM IDT)
• *Wolf M. (17/03/2016 10:07 PM IDT)
• **Danny Scheinerman (17/03/2016 10:48 PM IDT)
• **Tilo Anschütz (18/03/2016 09:16 AM IDT)
• *Florian Fischer (19/03/2016 01:39 PM IDT)
• **Nigel Brumpton (22/03/2016 08:35 AM IDT)
• Daniel Chong Jyh Tar (23/03/2016 04:32 AM IDT)
• *Fabian Lischka (23/03/2016 11:22 AM IDT)
• *Pål Hermunn Johansen (23/03/2016 09:14 PM IDT)
• Fabio Filatrella (27/03/2016 03:16 PM IDT)
• **Paul Vishayanuroj (28/03/2016 01:23 AM IDT)
• **Fabio Michele negroni (28/03/2016 02:46 PM IDT)
• Di Luo (28/03/2016 06:25 PM IDT)
• **Jamorn Horathai (29/03/2016 12:22 PM IDT)
• Claudio Hüni (29/03/2016 05:48 PM IDT)
• T.K. Chang (29/03/2016 09:30 PM IDT)
• **Leandro Augusto de Araújo Silva (29/03/2016 11:41 PM IDT)
• **Serge Batalov (30/03/2016 11:57 AM IDT)
• **Tom MacDougall (30/03/2016 06:06 PM IDT)
• Bruce M Fleischer (31/03/2016 02:13 AM IDT)
• *Christof Mroz (31/03/2016 02:21 AM IDT)
• Nguyen Ha Duy Henry (31/03/2016 06:08 PM IDT)
• **Muralidhar Seshadri (31/03/2016 06:11 PM IDT)
• Jason Lee (31/03/2016 07:05 PM IDT)
• Dan Salajan (31/03/2016 10:55 PM IDT)
• *Martin Sergio H. Faester (01/04/2016 01:45 AM IDT)
• Oscar Volpatti (01/04/2016 05:34 AM IDT)
• Junjiajia Long (01/04/2016 07:39 AM IDT)