Problems & Puzzles: Puzzles

Puzzle 603. p=(q*r+s)/2 JM Bergot made me notice that the prime p=113 can be expressed in 3 similar ways using 3 distinct odd primes in each way: (13*17+5)/2 = (11*19+17)/2 = (7*29+23)/2 = 113. Q1. Can some prime p be created in more than three such ways? In the Bergot's example the generating primes q, r & s, are only 8 distinct primes. Q2. Can you produce solutions using 9 distinct generating primes?

---

Contributions came from Hakan Summakoğlu, J.K. Andersen, W. Edwin Clark, Jan van Delden.

***

Hakan wrote:

Q1:
1:(5*11+3)/2=29
2:(3*17+7)/2=29
3:(3*13+19)/2=29
4:(5*7+23)/2=29

1:(3*19+5)/2=31
2:(5*11+7)/2=31
3:(3*17+11)/2=31
4:(3*13+23)/2=31
5:(3*11+29)/2=31

1:(3*43+5)/2=67
2:(3*41+11)/2=67
3:(5*23+19)/2=67
4:(3*37+23)/2=67
5:(3*31+41)/2=67
6:(7*13+43)/2=67
7:(3*29+47)/2=67

Q2:
(3*19+5)/2=(5*11+7)/2=(3*17+11)/2=(3*13+23)/2=(3*11+29)/2=31

***

J. K. Andersen wrote:

In total there are 21 ways to express 113 as (q*r+s)/2,
where q, r, s are distinct odd primes.
Here they are sorted by the largest of the primes:
(13*17+5)/2
(11*19+17)/2
(7*29+23)/2
(5*37+41)/2
(5*43+11)/2
(3*61+43)/2
(3*53+67)/2
(3*71+13)/2
(5*31+71)/2
(3*73+7)/2
(11*13+83)/2
(3*43+97)/2
(3*41+103)/2
(7*17+107)/2
(5*19+131)/2
(3*29+139)/2
(7*11+149)/2
(3*23+157)/2
(5*7+191)/2
(3*11+193)/2
(3*5+211)/2

Only the first 3 ways are shown in the puzzle which says 113 can be expressed
in 3 "similar ways". What must they satisfy to be considered similar?
The total number of ways quickly becomes large, for example 5473 for p=99581.

***

W. Edwin Clark wrote:

Trying all primes q,r,s, q < r, up to only the 100th prime (541) I get the following record for Q1. (With more patience I imagine one can find many more.)

Q1. The prime 317 can be express as 317 = (q*r+s)/2 in 39 distinct ways:
The 39 prime triples [q,r,s] that have this property are:

[3, 31, 541], [3, 37, 523], [3, 197, 43], [3, 59, 457], [3, 67, 433],
[3, 71, 421], [3, 79, 397], [3, 89, 367], [3, 101, 331], [3, 107, 313],
[3, 109, 307], [3, 131, 241], [3, 137, 223], [3, 151, 181],
[3, 157, 163], [37, 17, 5], [5, 31, 479], [5, 37, 449], [5, 43, 419], [5, 73, 269], [5, 79, 239], [5, 109, 89], [5, 97, 149], [7, 89, 11], [7, 29, 431], [7, 41, 347], [7, 83, 53], [7, 53, 263], [7, 71, 137], [11, 13, 491], [11, 31, 293], [11, 37, 227], [13, 47, 23],
[13, 29, 257], [13, 41, 101], [17, 19, 311], [17, 31, 107],
[19, 23, 197], [19, 29, 83]

Q2. The prime triples [31, 223, 229], [53, 131, 199], [67, 103, 241]
correspond to the prime 3571 and consists of 9 distinct primes. There are many primes that have this property.

***

Jan van Delden wrote:

My solutions: (# distinct [q,r,s],minimal p,list of [q,r,s]).

 

1,  11 [3,5,7]

2,  29 [3,13,19],[5,7,23]

3,  47 [3,19,37],[5,13,29],[7,11,17]

4,  83 [3,29,79],[5,19,71],[7,17,47],[11,13,23]

5, 131 [3,23,193],[5,31,107],[7,29,59],[11,19,53],[13,17,41]

6, 191 [3,37,211],[5,43,167],[7,29,179],[11,31,41],[13,23,83],[17,19,59]

7, 293 [3,29,499],[5,37,401],[7,47,257],[11,43,113],[13,41,53],[17,31,59],
[19,23,149]

8, 401 [3,37,691],[5,67,467],[7,53,431],[11,61,131],[13,41,269],[17,43,71],
[19,29,251],[23,31,89]

9, 479 [3,67,757],[5,61,653],[7,53,587],[11,79,89],[13,47,347],[17,43,227],
[19,41,179],[23,37,107],[29,31,59]

10,643 [3,59,1109],[5,47,1051],[7,109,523],[11,83,373],[13,43,727],[17,71,79],
[19,61,127],[23,53,67],[29,41,97],[31,37,139]

11,857 [3,89,1447],[5,79,1319],[7,59,1301],[11,73,911],[13,47,1103],[17,61,677],
[19,83,137],[23,67,173],[29,43,467],[31,53,71],[37,41,197]

 

Note: 113 has 15 solutions having length 4 with all primes distinct, one of which is: [3,23,157],[5,19,131],[7,17,107],[11,13,83]

 

If one tries to find solutions with distinct primes of length n of the form [p[i],p[j], some s] with i+j=2n+3 and i in [2..n+1] like the solutions for p=11 and 113 above,

the only other (minimal) solutions are:

 

2, 47 [3,11,61],[5,7,59]

3, 59 [3,17,67],[5,13,53],[7,11,41]

 

If n>=5 there is (probably) at least some prime t (probably always 3) for which the residues of the s mod t (or q.r mod t) form a complete set.

***