Problems & Puzzles: Puzzles

Puzzle 655 pq+rs, perfect square.

In one of the the Prime Curios! pages from Caldwell & Honaker, Jr. I found this curio:

Let p < q < r < s be consecutive primes. The least prime p for which pq + rs is a perfect square is 203233.

Q1 Find three more cases.

BTW see our puzzle 498.

Contributions came from Ryan Bailey & Emmanuel Vantieghem


Both weren't able to find more solutions than the reported one going up to 21940132061 and to 31*10^9, in their respectively search.


Jan van Delden wrote on May 11, 2018:

I tried to find solutions to:


pq+rs=y^2 (I)
ps+qr=y^2 (II)
pr+qs=y^2 (III)


with p,q,r,s consecutive primes.

The last two equations are added because of a remark of Farideh in Puzzle 498.




At first I decided to use a Sieve. I didnít find another solution with p<4000*2^32.
So time for a different attack. And I followed the suggestion by Carlos in Puzzle 498:




where a=q-p, b=r-p, c=s-p, the prime gaps of q,r,s relative to p, so 0<a<b<c.

From this we have that [0,a,b,c] mod 3 must be admissible, it may not form a complete residue set mod 3.


Multiply by 2:


4p^2+2p(a+b+c)+2bc=2y^2 (*)

We know that 2|(a+b+c) and that 4|bc, so the expression can be divided by 4 and y must be even y=2z.



Suppose that 4|(a+b+c). We can than complete the square:


The right hand side is even and the left hand side is odd.


So we must have that a+b+c=2 mod 4. Letís complete the square on (*) directly:




Or after some manipulations:


x^2-2y^2=-d  (**)




g = (a+b+c)/2 
d = 2bc-g^2   

x = 2p+g


This diophantine equation (**) is well known. I would recommend reading The Diophantine Equation x^2-Dy^2=N, D>0 by Keith Matthews.
In it he describes the method of simple continued fractions to solve this type of equation, without the necessity of using the fundamental solution of Pellís equation (d=+/-1) in order to describe all solutions.


In our case, a necessary condition for solutions to exist is x^2=2 mod (|d|).
So this restricts the possibilities of d to those d for which 2 is a square residue mod abs(d).
If |d| is prime the Lengendre symbol (2/|d|) should equal 1 to allow |d|.
If |d| is not prime the Jacobi symbol (2/|d|) excludes cases if the result equals -1.


The method requires to find all roots r in (0..|d|-1) such that r^2 = 2 mod |d|.

[If d=+/-1 one could use the fundamental solution to the resulting Pell equation]

So if the Jacobi symbol returns 1, it is not conclusive, one should just try to find roots r, we need them anyway.


The method of continued fractions is used on (r+sqrt(2))/|d| for all roots  r in a reduced residue set mod |d|.


The other two equation types (II,III) are similar but have a different d:

II) swap  a-c
III) swap a-b


Search bounds:

I searched all [a,b,c] with c<= 500, using the conditions on a,b,c as stated before.

For these I computed  a list of values of d (having 2 as a square mod |d|) and for each d I kept a list of values of g and the equation type that generated this combination (d,g). For every root r belonging to a value of d I tried to find solutions x such that:

p=(x-g)/2 is prime and compute a,b,c belonging to this p and itís realised values g* and d*. [For every possible g]
Finaly check g* and d* against the values (g,d) used to generate this solution (x,p), using the correct type of equation belonging to (d,g).


I found 16589 different d. The total number of combinations (d,g) is equal to  572122.


I used a maximum of 105 iterates. (Limiting the primes p to approximately 40 digits). However I found no other solutions.


As an example:


For the given solution 203233, we have (a=16,b=46,c=60), so d=1799 and g=61.
Within my search bounds for [a,b,c] there are 132 values of g, one of which is 61.

1799 has 4 roots r (60,711,1088,1739) with r^2=2 mod 1799.
The root 711 defines the number (711+sqrt(2))/1799.

The associated simple periodic continued fraction is [0; 2 1 1 9 2], the last 2 repeats indefinitely.
Its value as a fraction terminated at iterate 14 is equal to 113835/287458.
So x = 113835*1799 Ė 287448*711 = 406527 is a solution to (A). The transform (x-g)/2 now gives a prime p.
Which checks out o.k.


Estimate of number of [a,b,c] with c<=N.


Admissible mod 6: [0,0,0],[2,2,2],[4,4,4],[2,0,0],[0,2,0],[0,0,2],[4,0,0],[0,4,0],[0,0,4],[2,2,0],[2,0,2],[0,2,2],[4,4,0],[4,0,4] [0,4,4]
There are 15 combinations [a,b,c] with are admissible mod 6 (or 3), out of 3^3=27 combinations.


About half of the sums a+b+c are 2 mod 4.

One can choose N/2 different even numbers 0<n<N.
The total number of [a,b,c] to choose from is smaller than (N/2)^3/6=N^3/48. [Can be made precise].

So I would estimate this with N^3/48*15/27*1/2 = 5/864*N^3.

Some have to be descarded because we need d to have a square root of 2. Testing reveals that although we can discard about half the d, this is not true for the [a,b,c], the reason is that we have 3 d-values (depending on the type of equation) for 1 set of [a,b,c].

P(keep [a,b,c] for any type)=1-P(discard [a,b,c] for one type)^3=7/8

Leading to the final estimate 35/6912*N^3, which is too large, but this gives a fair clue to the amount of work needed.




All d>0 are of type I. So type II,II have d<0.

The situation d=-1 is possible. In fact I found 138 different values of g belonging to this d. All are type I.
It would be helpful if one could prove that all these periodic continued fractions have period 1 with periodic part 2.
Because d and g comprise 2 parameters derived from 3 parameters [a,b,c] this routine actually checks more combinations [a,b,c] than those used to compute d and g.


To do:

Either broaden the horizon and allow a larger set of (d,g) or increase the number of iterates (to check larger prime solutions) or both.
Better would be to try and find a deeper relation to restrict the computations involved.

As a sidenote I used Maple. But itís memory management went Ďout of controlí. So taking a next step would entail rewriting the routine in c, giving me more control on this aspect.


Jan van Delden wrote on May 23, 2018:

I changed my routine:
- The admissible d are computed differently. d is admissible if and only if d has prime divisors p=+/-1 mod 8.
- It only computes roots r with 0<=r<=d/2 and uses these to find the primitive solution by using the associated continued fraction of (r+sqrt(2))/|d|.
- This primitive solution is used to find solutions for roots r in -d/2<=r<=d/2, upon using the fundamental solution of the Pell equation x^2-2y^2=1.
  A primitive solution, x0+y0*sqrt(2) is multiplied by eta^n, with eta=3+2*sqrt(2), the fundamental solution.
  Or, for negative r, x0-y0*sqrt(2) or -x0+y0*sqrt(2) is used, depending on the sign of d.
- One iteration using the new method has the same effect as 2 iterations using the old method (and is faster because one can precompute the values of eta^n).
I found the following solutions with a<b<c<1000 with a maximum of 200 iterations:
Type I) p*q+r*s=m^2:
Type II) no solutions, given the search area and maximum # of iterations.
Type III) p*s+q*r=m^2:
I checked all primes with PRIMO.



Records   |  Conjectures  |  Problems  |  Puzzles