Problems & Puzzles: Puzzles

Puzzle 148.  Product of primes - 1, a square

Jean Brette has examined an apparently slight variation of the Puzzle 137 producing a very nice, interesting and completely distinct puzzle.

This time he asks for a sequence of n distinct positive numbers {p1, p2, p3, ..., pn} such that each of the following numbers:

p1 - 1
p1.p2 - 1
p1.p2.p3 - 1
...
p1.p2....pn - 1

are respectively equal to the square numbers k12, k22, k32 ,.., kn2

As a matter of fact Jean has devised a clever algebraic approach to demonstrate that - if no other restriction is imposed to the set of numbers {p1, p2, p3, ..., pn } - as being primes or other restriction - then there are infinite distinct infinite sets of these numbers.

But what happen if the numbers {p1, p2, p3, ..., pn } are asked to be distinct prime numbers?

Well in this case, the Jean's algebraic approach also provides a technique useful to construct these sets of primes if you count with independent means to test the primality of the numbers generated by that technique.

An example of 7 members calculated by Jean is this one:

pi = {17, 53, 14177, 817559713, 2673428525403693377, 11167531389350953849243330653921141761, 1247137573321388456507926990396681748026131699540161887534542768799725133, ...}

Question:

a) Can you discover the Jean's (or your own) technique to generate a set of prime numbers {p1, p2, p3, ..., pn } according to the conditions above stated?

b) What is the smallest (*) set of primes {p1, p2, p3, ..., pn } that satisfy the conditions above stated?

It happens that Jean has explained to me his technique, and - after knowing it - I have came to the following conjecture:

(Conjecture): for each proper p1 (that is to say, for each prime p1 equal to a square plus 1) you can always generate an infinite sequence of primes p2, p3, ... that satisfy the above stated condition 

c) Can you prove or disapprove the previous conjecture?

d) The set of proper primes for this puzzle, p1 = x2 +1, is finite or infinite?

Jean has constructed some limited sequences of primes {p1, p2, p3, ..., pn } that satisfy not only the conditions above stated but also the following additional condition: all ki values are also primes.

Another example of 7 members calculated by Jean is:

pi = primes = {5, 2, 5, 37, 46681, 167191851817, 2079167507064726254233}
ki = primes = {2, 3, 7, 43, 9293, 3799824107, 173263958925860345293}

e) Do you think that the Conjecture previously stated remains with this compound condition (pi & ki are prime numbers)

________
(*) One set of primes A is smaller than other set of primes B if both have the same quantity of elements (nA = nB) and SA is less than SB, where SX is the sum of the elements in the set X


Solution

Felice Russo has sent the following contributions to some of the questions posed here:

question a: I have found the following procedure to find easily the set that you requested (is the same of Brette?). First of all let's observe that since p1-1 must a square then p1 must be a prime of form k^2+1.

Then we must find a second prime such that p1*p2-1 is a square, that is p1*p2=t^2+1. But p1=k^2+1 and then p2=t^2+1/K^2+1. So we must just  to search the value of t, knowing already k, such that p2 is prime. Once we find this value we can go ahead. Now we must find a third prime p3 such that p1*p2*p3-1 is a square, that is p1*p2*p3=l^2+1. But we know that p1=k^2+1 and p2=t^2+1/k^2+1 and then p3=l^2+1/t^2+1. But we already know t and then the only thing to do now is just search the value of l such that p3 is prime and so on........

For example for p1=2 I have found in less than 1 minute the following set: (2,5,17,89,557,245443) with the following simple algo:

5 cls
6 A=2
10 I=3
20 X=I^2+1
30 if X@A=0 and prmdiv(X\A)=X\A then print X\A:A=X
40 if I>10^8 then end else I=I+10:goto 20

question c): As already I proved in the my previous message all the primes of Brette sets are of the form p=(j^2+1)/(k^2+1) where j and k are integers (j=1,2,3,4,5..... and k=0,1,2,3,4,5.......).

Then what I did was just to calculate the counting function b(j,k) for j between 1 and 10^5 and k between 0 and 100. As you can see in the attached plot the function b(j,k) goes quickly to zero for k around 50, but anyway for small k values the counting function goes to the infinite (even though always more slowely as k tend to about 50). So being the number of primes of form p=(j^2+1)/(k^2+1) infinite for small values of k I think that your conjecture is well posed.

question d: according to a conjecture of Hardy and Littlewood there exist infinitely many primes of the form n^2+1. Moreover the counting function of those prime is given by p(x)=C*sqrt(x)/ln(x) where p(x) is the number of primes of the form n^2+1 less than x. The constant C is equal to 1.37281346.....

***

This is my comment to him, regarding the question a):

I saw your approach to the puzzle 148. It's an interesting combination of brute-force & shortcut. Evidently you can not go too far with this approach (and I'm not referring to the code here) because the primes start growing to fast each time more.

His contribution to question d) is totally correct: Nobody knows if the primes of the form n^2+1 are infinite or not, except the positive plausibility hanging from the Hardy & Littlewood's conjecture.

What do you think about the Russo's argument to the question c)?

***

Ken Wilke discovered by his own the algebraic core of the Brette's approach. This is his email (12/8/2001):

"My solution relies on the identity   (kj2 + 1)(a2 + b2 ) =(a kj + b)2 +  (b kj - a)2 where Pj+1 = a2 + b2. Unless Pj+1 = 12 + 12 = 2, Pj+1 is odd and a and b have opposite parity. Then once Pj is known, we construct  Pj+1 by using the identity in the following manner:

            1. Set b kj - a = +/-1 so that b kj +1 = a..

            2. Choose a possible value of b, determine the corresponding values of a and check to see whether a2 + b2 is prime; i.e whether (b kj +/- 1)2 + b2 is prime.

            3. The requisite testing can be carried out by using UBASIC programs. I used the Rho factoring program which shows possible primes as pseudo-primes. This program was modified to test numbers of the form (b kj +/- 1)2 + b2 . If the program started factoring, it was stopped and a new value was tested until a pseudo-prime appeared. Then the APRT program was used to verify that any pseudo-prime was actually prime.

  I suspect that the following sequence of Pj , kj  satisfies your question (b).

  ( P1 , k1 ) = (2 , 1), ( P2 , k2 ) = ( 5, 3),  ( P3 , k3 ) = ( 17, 13), ( P4 , k4 ) = (197, 183), ( P5 , k5 ) = ( 33857, 33673), ( P6 , k6 ) = ( 10204636333, 3401579117), ( P7 , k7 ) = (46282961943235682293, 2314180975019420263) and ( P8 , k8 ) = (21421734340567338534571003886537637733, 10710867170283669264971320968249398603).

Of course the sequence can be continued, but the computations become horrendous.

To illustrate the method, start with  P1 = 2 and  k1 = 1. Then (k12 + 1)(a2 + b2) =(a + bk1 )2 + ( bk1 - a)2 . Setting a = bk1  +/- 1 , we take b = 1 and the plus sign so that a > 0 .

Hence a = 2 and P2 =   a2 + b2 = 22 + 12 = 5. The k22 =  P1* P2 - 1 = 32 so k2 = 3. Next starting with k2 = 3 we have (k22 + 1)(a2 + b2 ) =(ak2 + b)2 +  (bk2 - a)2 =  (3a + b)2 +  (3b - a)2. Setting a = 3b +/- 1. Taking b = 1 yields a = 2 or 4. Hence a2 + b2 becomes 5 or 17 respectively. We reject a = 2 since 5 already appears in our sequence of Pj. Trying b = 2 yields a = 5 or 7 with corresponding values of  a2 + b2 = 29 and 53 respectively. I chose b=1 and a = 4 which given a minimal value of P3 = 17 and correspondingly we have k3 = 13.

Proceeding in a similar fashion, we set (k32 + 1)(a2 + b2 ) =(ak3 + b)2 +  (bk3 - a)2 =  (13a + b)2 +  (13b - a)2. Setting a = 13b +/- 1. Taking b = 1 yields a = 12 or14. Hence a2 + b2 becomes prime only for a = 14 and b = 1. Hence (P4 , k4 ) = (197, 183).

Proceeding in a similar fashion, we set (k42 + 1)(a2 + b2 ) =(ak4 + b)2 +  (bk4 - a)2 =  (183a + b)2 +  (183b - a)2. Setting a = 183b +/- 1. Taking b = 1 yields a = 182 or184. Hence a2 + b2 becomes prime only for a = 184 and b = 1. Hence ( P5 , k5 ) = (33857, 33673). { The next prime value for P5 occurs for b = 5 using the minus sign in choosing a which leads to P5 = 835421.)

Proceeding in a similar fashion, we set (k52 + 1)(a2 + b2 ) =(ak5 + b)2 +  (bk5 - a)2 =  (33673a + b)2 +  (33673b - a)2. Setting a = 33673b +/- 1. Taking b = 3 with a minus sign yields a = . Hence a2 + b2 becomes the prime 10204636333. Hence ( P6 , k6 ) = (10204636333, 3401579117). The values of (P7 , k7 ) and (P8 , k8 ) were developed by repeating the process.

 

***

Later Mr. Wilke added:

Using Felice Russoís idea as a springboard, consider the two sequences P1 ,  P2 , . . . , Pn, and k1 , k2 , . . . , kn where each Pj is a prime of the desired type so that P1 * P2* . . . *Pj, = kj2 + 1. Then since kj+12 + 1 = P1 * P2* . . . *Pj+1, = Pj+1(kj2 + 1), we must have kj+12 + 1 0 = (kj2 + 1) mod (kj2 + 1). Hence  kj+1 = kj mod ( kj2 + 1).This congruence implies that for any given kj,  kj+1 can be found among the solutions of the congruence x2 + 1 = 0 mod (kj2 + 1). Then it becomes necessary only to check these solutions to see if an appropriate prime Pk+1 appears. We shall use this fact to generate the answer to part (b).Tthe sequence of 7 smallest distinct primes satisfying (b) is {2,5,17,13, 97, 8761, 6628133}. The corresponding values of k are {1,3,13,47,463,43337,111571803}.

Starting with P1 = 2 =12 + 12, we see that k2 = k1 = 1 (mod 2). To find a distinct prime P2 we take k2 = 3. Then P2 = (k22 + 1) = ((k12 + 1) = 5 which is prime. Then the congruence x2 + 1 = 0 (mod 10) has the solutions x = 3,7 (mod 10). Here we take k3 = 13 since the other value donít produce a distinct prime.k3 = 13 yields P3 = 17. The solutions of x2 + 1 = 0 (mod 170) are  x = 13,47,123,157 (mod 170). Taking k4 = 47 yields P4 = 13. (Russoís solution corresponds to taking k4 = 123.)The solutions of  x2 + 1 = 0 (mod 2210) are x = 47,463, 837,863,1347,1747, 2163 (mod 2210). Taking k5 = 463 yields P5 = 97. The three smallest solutions of  x2 + 1 = 0 (mod 214370) are x = 463,25683, 43337 (mod 214370). Taking k6 = 25683 which yields P6 = 3077 = 17 * 181. Hence we take k6 = 43337 which yields P6 = 8761 which is prime. Finally proceeding similarly, we find k7 = 111571803 (mod 1878095570) which yields P7 = 6628133.

This process works well since the solutions of the congruence x2 + 1 = 0  mod (kj+12 + 1) can be made to depend on the solutions of the congruences  x2 + 1 = 0  mod (kj2 + 1) and x2 + 1 = 0  mod (Pj2 + 1) which are combined using the Chinese remainder Theorem.

Hence the sequence of 7 smallest distinct primes satisfying (b) is {2,5,17,13, 97, 8761, 6628133}. The corresponding values of k are {1,3,13,47,463,43337,111571803}.

***

I asked Ken Wilke to comment about the conjectures I inserted in this puzzle. Here are his comments:

"If only the values of p are required to be prime, I strongly suspect the an infinite sequence of primes can be constructed using the method outlined in my first submission. The key idea is that for each value of k found, we have (k,1) =1 , where (k,1) is the greatest common divisor. Then one would invoke Dirichlet's theorem that: if ( a,b) = 1 with a > 0 and b > 0, then there are infinitely many primes of the form a + nb where n is a positive integer.... If you are talking about the conjecture in (e), it looks like an interesting spin-off of my initial attempt at part (b) of problem 148. Looking at the sequence of k values for my "sequence of smallest primes" satisfying (b), the first few values of k are prime, but 43337 and 111517803 are composite. I suspect that finding a long sequence in which both the values of p and k are prime would be very difficult. Be requiring the p values to be prime, the choices for the corresponding values of k are severely limited. In particular, the factor 3 seemed to appear often. But with a proper choice of a prime as a starting point, who knows...."

***

 

 


Records   |  Conjectures  |  Problems  |  Puzzles