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

[Tim Peters]

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.

What about solutions with an odd number of digits? They come "for free", as
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/
>>
>