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

[Tim Peters]

OK - changing the algorithm to build suffixes (essentially) depth-first up
to a digit limit, instead of breadth-first, reduced the memory burden from
crushing to trivial. Unless there's an error, there are only 3 essentially
different solutions with no more than 20 digits:

      9678692507732 # 13 digits
 899552419664035532  # 18 digits
9623556076911958628  # 19 digits

"Essentially" means that any number of trailing zeroes can be added to any
solution to get other solutions.

Empirically, checking all the possibilities through k decimal digits
appears to create (very roughly) sqrt(10^k) feasible suffixes. For k=20
above, about 4.4 billion were generated.

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/
>>
>