Problems & Puzzles: Puzzles

Puzzle 340. Resta's approach to Puzzle 337

Giovanni Resta has discovered an approach in order to get really large solutions to Puzzle 337, devoted to find primes p inside p2.

I have found it as interesting as to pose a new puzzle about the same issue.

Just in order you calibrate the goodness of the Resta's approach I will tell you that Resta has found prime solutions as large as 1339 digits!..

Here are the solutions that he has already gotten:

D=14 p=50385563791193
D=31 p=1239238634156610518519655166771
D=32 p=36558979464205583642747845341043
D=50 p=31765260352472360498918220762893129248965293653303
D=76 p=79241666225702895015316307770939879469537483381507
D=80 p=46693111837955691724224403589002523102938436567844
D=118 p=68442887702247601900968863730447448958697633137625
D=307 p=26669583720733387815278860507791203199363591542992
D=1339 p=826208...<omitted>...71751


503855637911932 = 2538705038556379119304363249

and so on.

Here is his approach:

Let us suppose that x is a solution to our problem, that is, the digits of x are contained in x^2. In particular let us suppose that x^2 has the following special structure:


i.e., a "prefix" which has value k (and digits KKK..K), then some zeroes, then the digits of x (XXX..XX) then some zeroes.
(For example, if x=456 and k=38, we can have a structure like x^2 = 45600038000. Of course this is impossible, but just to give the idea).

If this was the case, then x and k must satisfy this equation:
x^2 = k*10^p + x*10^q, where the powers of ten (10^p and 10^q) are are clearly dependent on the numbers of digits of x^2 and the number of trailing zeroes.

Now we are ready to search for x.

If we fix a prefix k and two powers of ten 10^p and 10^q we can try to see if there is an x which satisfy the equation above, at least approximations to x. Indeed, if the approximation is good enough, then x^2 will contain some dirt in the last digits, but not too much and maybe the x in the middle will be preserved.

For example, let us suppose that we fix k=4482, and p=20 and q=6. We obtain x=669477908132.82... Let us try with x = 669477908132. We have x^2 = 448200669476798631729424
We can see that the prefix it is right there. Then there are some zeroes and then x starts well: 66947... but then there is a 6 instead of a 7 etc. The number x is clearly too small. So we try with x+1 = 669477908133 and (x+1)^2=448200669478137587545689.In this case the number it is too large, and the game is over.

We try with another set of exponents. p=12 and q=6. and obtain x=66952740. In this case x^2=4482669393507600, it's too small.
But then x+1=66952741 and (x+1)^2=4482669527413081 is ok (as we already know, since this was one of Rivera's solutions).

I have searched in this way for several values of the prefix and some choices of the exponents p and q.

In particular, choosing the values of q near to p/2, we obtain tentative values of x^2 in which there are few (if any) zeroes between the prefix k and the occurrence of x in x^2.

I've not tested all the possible exponents, but I noticed (in particular searching for the most common odd, instead of prime,
solutions) that most of them were indeed found when q was 1 or 2 apart from p/2. The intuitive reason is that in this way we maximize the number of digits "after" x in x^2, so we minimize the probability that the perturbation in x^2 induced by the approximation of x, will not affect the digits of x inside x^2.


1. Find larger & larger primes of this type using the Resta's approach (or a reformulated one)

2. Do you devise a clever approach as this one, in order to find p primes reversed in p2?




Records   |  Conjectures  |  Problems  |  Puzzles