# [seqfan] Re: Squares with even-positioned digits matching the original number

Tim Peters tim.peters at gmail.com
Tue Dec 5 06:59:46 CET 2023

```There's more exploitable mathematical structure here than I realized at
first. This gives me increasing confidence that the "shortcut"
feasible-suffix approach isn't missing anything.

Key: it turns out that, for a feasible suffix F with an even number k of
digits (k >= 2), and not ending with 0, F can always be extended to a k+2
digit feasible suffix. In fact, that can always be done in either 8 or 12
different ways. No trial-and-error is needed - the new digit pairs are
found by solving linear equations modulo 100, and goes fast

So my current code starts with the 2-digit feasible suffixes (there are
only 4: 28, 32, 78, and 82), and builds those up "on the left" 2 digits at
a time (either or both of which may be 0).

Since the average of 8 and 12 is 10, it's reasonable to expect that these
give rise to about 4*10 = 40 4-digit feasible suffixes. In fact there are
36.

Then I expect about 36*10 = 360 6-digit ones. In fact there are 368. And so
on.

This wholly explains the empirical "grows kinda like the square root of
10^k" observation.

A surprise: there is no pruning with an even number of digits. Every branch
of that tree grows without bound, with a branching factor of 8 or 12 at
each node. Does every branch eventually reach a full solution? Empirical
evidence says "sure seems unlikely!", but no clue how to prove it either
way.

even-length suffix solutions that happen to have a leading 0 digit.

I'm running code through 24 digits now. It's coded in Python, so will take
a few days to complete (although, under PyPy, it's generating about a
million feasible suffixes, and also checking to see whether they're full
solutions, per second).

On Fri, Dec 1, 2023 at 10:46 PM Tim Peters <tim.peters at gmail.com> wrote:

> FYI, I found only 7 solutions with no more than 18 decimal digits, but all
> save one are trivial variants of the one you already found:
>
> 9678692507732
> 96786925077320
> 967869250773200
> 9678692507732000
> 96786925077320000
> 967869250773200000
> 899552419664035532  NEW ONE
>
> I'm not certain there aren't others < 10^18 - the code was mildly clever
> to avoid needing to check every number, and "clever" can hide errors.
>
> Short course: can any solution end with, say, 27? No: modulo 100, if n
> ends with 27, n^2 ends with 29. So n can't be a solution: throw away the
> trailing 9 in 29, showing that n must end with 2. But n ends with 7.
>
> In this way, longer and longer feasible suffixes are constructed, tacking
> on a digit "on the left", one at a time.
>
> This saves an enormous amount of futile checking, but by the time all
> 18-digit feasible suffixes were constructed, there were over 500 million in
> play. At that point I was running out of RAM.
>
> The original example you found was discovered in well under 10 seconds.
>
> On Fri, Dec 1, 2023 at 1:54 PM David Radcliffe <dradcliffe at gmail.com>
> wrote:
>
>> Hi all,
>>
>> I recently came across sequence A326418, which is described as
>> "Nonnegative
>> numbers k such that, in decimal representation, the subsequence of digits
>> of k^2 occupying an odd position is equal to the digits of k." I was
>> wondering about the analogous problem for even positions, but that
>> sequence
>> is not in the OEIS.
>>
>> I performed a search up to 10^16, and the only example I found was k =
>> 9678692507732, excluding multiples of 10.
>>
>> This is a term because k^2 = 93677088659227550879783824, and if we remove
>> every other digit from k^2, starting with the units digit, we get back to
>> 9678692507732.
>>
>> Are there other solutions? I am intrigued by this sequence because the
>> first term is so large, but I don't know enough terms to propose it for
>> inclusion in the OEIS.
>>
>> - David
>>
>> --
>> Seqfan Mailing list - http://list.seqfan.eu/
>>
>
```