[seqfan] Re: {5, 235, 72335}^2 = {25, 55225, 5232352225}

[David Wilson]

zak seidov wrote:
> David, It seems that your results are missed,
> or what else does your post mean?
> thx, zak 
>   
I'm guessing that you are asking for a more detailed explanation of my 
post, so here goes.

We are looking for numbers n such that n and n^2 are composed entirely 
of prime digits.

We notice that for any k >= 1, the last k digits of n determine the last 
k digits of n^2. For example, if n ends in the 3 digits 339, n^2 ends in 
the three digits 921.

We can use this observation to narrow our search. For example, if n ends 
in 2, n^2 ends in 4, so that n^2 cannot be composed of prime digits. 
Thus our sequence cannot contain any number that ends in 2. Similarly, 
if n ends in 3 or 7, n^2 ends in 9, so our sequence cannot include 
numbers that end in 3 or 7.

The only other possibility is numbers that end in 5. If n ends in 5, 
then n^2 ends in 5, so there might be numbers in our sequence that end 
in 5. In fact, when we square 5, we get 25, so 5 is in our sequence.

Now we check two-digit numbers. Since 5 is the only possible ending, we 
check n = 25, 35, 55 and 75. For each of these, n^2 ends in 25, so all 
of them are possible endings of sequence elements. However, we can 
verify that none of them is an element itself.

Now we check 3-digit endings. The candidates are 225, 235, 255, 275, 
325, 335, 355, 375, 525, 535, 555, 575, 725, 735, 755, and 775. When we 
square these, we find that n^2 ends in 025, 225, or 625. Only those n 
for which n^2 ends in 225 are permissible endings, these are n = 235, 
335, 535 and 735, so n must end in one of these. Squaring these, we find 
that n = 235 is in our sequence.

We continue on in this way. For k digits, we take the (k-1)-digit 
endings, prepend 2, 3, 5 and 7 to get the candidate k-digit endings. We 
square these endings, and if a non-prime digit shows up in the last k 
digits of the square, we reject the ending. If the square entirely 
consists of prime digits, we add the ending to our sequence.

I wrote a program that used this technique to find elements of your 
sequence. It found 5, 235, and 72335 found and then terminated, meaning 
it had eliminated all possible endings and found all possible elements. 
For this reason I believed these were the only three elements. But when 
you asked for a proof, I checked my program and found a bug. After I 
fixed the bug, the program found your three elements, but continued 
searching.

By looking at the program, I found that if n has the k-digit ending 
3333...3335, then n^2 has the k-digit ending 2222...2225. This means 
that 3333...3335 is always a possible ending, so there are an infinite 
number of possible endings, and I can never be sure I have all the elements.

I ran this program up to 26 digits and did not find any additional 
elements larger than 72335. Under the simplifying that digits in the 
first half of n^2 are uniformly distributed, I estimate the probability 
of finding any larger elements to be 10^-10 or smaller. In other words, 
it is quite unlikely that there are any more elements, and probably not 
worth the search effort.