[seqfan] Re: Ultra Square Palindromes

[M. F. Hasler]

On Sun, Oct 23, 2022 at 11:02 AM <hv at crypt.org> wrote:

> Does anyone know of an easy way to look at the n-digit ending of some
> square (in decimal) and predict what digits can precede it in (n+1)-digit
> endings?
>

I don't have a satisfying answer, but I asked my computer and here's what
it said:

A very few n-digit endings are exceptional concerning the digits that can
precede,
The majority (all with the same parity) can be preceded by any of the
digits 0..9,
The endings of the other parity can be (and are) preceded either
by any of the 5 even digits 0,2,4,6 or 8, or by any of the 5 odd digits
1,3,5,7,9.

For n=2, we have A000993(2) = 22 possible endings:
ending 00 can be preceded by any of  [0, 1, 4, 5, 6, 9],
ending 25 can be preceded by any of [0, 2, 6]
endings { 01, 09, 41, 49, 81, 89 } can be preceded by any even digit
endings { 21, 29, 61, 69 } can be preceded by any odd digit
The 10 even endings except 00 can be/are preceded by any of the digits 0..9

For n=3, there are A000993(3) = 159 endings:
* The following three exceptional endings and possible "left neighbors":
000 : { 0 } ;  500 : { 2 } ; 625 : { 0, 5 }

* The following 50 endings can be preceded by any odd digit only:
024, 044, 056, 076, 104, 124, 136, 156, 184, 204, 216, 236, 264, 284, 296,
316, 344, 364, 376, 396, 424, 444, 456, 476, 504, 524, 536, 556, 584, 600,
604, 616, 636, 664, 684, 696, 716, 744, 764, 776, 796, 824, 844, 856, 876,
904, 924, 936, 956, 984

* The following 54 endings can be preceded by any even digit only:
004, 016, 036, 064, 084, 096, 100, 116, 144, 164, 176, 196, 224, 244, 256,
276, 304, 324, 336, 356, 384, 400, 404, 416, 436, 464, 484, 496, 516, 544,
564, 576, 596, 624, 644, 656, 676, 704, 724, 736, 756, 784, 804, 816, 836,
864, 884, 896, 900, 916, 944, 964, 976, 996

The other 52 (odd) endings can be preceded by any digit.

For n=4, there are A000993(4) = 1044 endings:
* The following exceptional endings and possible "left neighbors":
0000: { 0, 1, 4, 5, 6, 9 } ; 0625 : { 0, 3, 4, 5, 8, 9 } ; 2500: { 0, 2, 6
} , 5625 :  { 0, 1, 2, 5, 6, 7 }.

* 128 endings (0084, 0116, 0244, 0276, 0404...) can be preceded by any odd
digit only.
* 132 endings (0004, 0036, 0100, 0164, 0196, ...) can be preceded by any
even digit only.
* All 780 other (odd) endings can be/are preceded by any/each digit in 0..9.

I don't know whether this can help -- or maybe rather lead to the
conclusion that this is not an efficient approach, since it seems that in
most cases, any digit 0..9 is possible as left neighbor.

- Maximilian