Problems & Puzzles: Puzzles

 

Puzzle 831. Rings of primes.

Dmitry Kamenetsky sent the following nice puzzle.
Staring with a ring of 4 integers compute the following ring adding the three contiguous integers just above in the previous ring. Continue while in each ring there is at least one prime number.

Example: 4 rings, 8 primes.

1 3p 5p 7p - ring 1
11p 9 15 13p ring 2
33 35 37p 39 ring 3
107p 105 111 109p ring 4
 
The next layer would be (321,323,325,327), but since all these numbers are composite we are done.

Q1. Find a ring of 4 odd numbers that produces the most layers with at least one prime in each layer including the starting one.


Contributions came from Fred Schneider, Jeff Heleen, Jan van Delden, Emmanuel Vantieghem and Dmitry Kamenetsky

***

Fred  wrote:

I found a ring of length 17 for [11, 31, 221, 241]
11p 31p 221 241p

283p 263p 493 473

1019p 1039p 1229p 1249p 

3307p 3287 3517p 3497

10091p 10111p 10301p 10321p 

30523 30503 30733 30713p 

91739 91759 91949 91969p

275467 275447p 275677p 275657p

826571p 826591 826781 826801

2479963p 2479943 2480173 2480153 

7440059 7440079 7440269 7440289p

22320427 22320407 22320637p 22320617

66961451p 66961471p 66961661 66961681

200884603p 200884583p 200884813 200884793 

602653979 602653999 602654189p 602654209p

1807962187 1807962167 1807962397p 1807962377 

5423886731 5423886751p 5423886941 5423886961

Then it fails on ring 18:

16271660443 16271660423 16271660653 16271660633

 

***

Jeff wrote:

For puzzle 831: using odd numbers between 1 and 99 the most rings
I found was for 3, 9, 29, 89 with 22 rings.

 3          9          29          89 
 41          101          121          127 
 263          269          289          349 
 821          881          901          907 
 2603          2609          2629          2689 
 7841          7901          7921          7927 
 23663          23669          23689          23749 
 71021          71081          71101          71107 
 213203      213209      213229      213289 
 639641      639701      639721      639727 
 1919063      1919069      1919089      1919149 
 5757221      5757281      5757301      5757307 
 17271803      17271809      17271829      17271889 
 51815441      51815501      51815521      51815527 
 155446463      155446469      155446489      155446549 
 466339421      466339481      466339501      466339507 
 1399018403      1399018409      1399018429      1399018489 
 4197055241      4197055301      4197055321      4197055327 
 12591165863      12591165869      12591165889      12591165949
 37773497621     37773497681     37773497701     37773497707
 113320493003     113320493009     113320493029     113320493089
 339961479041     339961479101     339961479121     339961479127
 

Since the only requirements are that the numbers must be integers
and at least 1 prime per layer, I also tried with negative 
numbers. Using integers from -99 to 99 I found 5 more solutions 
with 22 layers...

***

Jan wrote:

Number of layers 34, for [457,827,3319,7547].
This is the maximum for a solution starting with prime numbers smaller than 10^4.
[So the number of combinations tested is of the order  pi(10^4)^4/24]
 
I also searched for solutions with three primes, starting with the number 1:
Number of layers 31, for [1,5179,5843,7457], with the same bound on the primes.
[So the number of combinations tested is of the order pi(10^4)^3/6]
 
If one writes the numbers as a[i,j], with i the layer and j in [1,2,3,4]. It’s easy to see that if we renumber the next layer we may write:
a[i+1,j]=S[i]-a[i,j]  with S[i]=sum(a[i,j],j=1..4). In this way it is possible to write:
a[i+1,j]=f(i)*S[1]+/- a[1,j] where the +/- sign depends on the parity of i and f(i) could be given explicitly.
 
At first I thought this might help to reduce the number of primes to test. This is true, however there are a few problems with this:
-    You require only one prime for one value of i. (So eliminating all (small) divisors  of f(i) as a choice for the a[1,j] for i<=k, for some bound k, excludes possible solutions)
-    For small values of k the reduction in computing time is not very big.

 

***

Emmanuel wrote:

I examined all rings with entries < 1000  and the best I found was
   {107, 169, 227, 967}
wich gives 32 layers.

 

***

Dmitry wrote:

Here are my best results. I found a ring with 39 layers that produces 53 primes:

 
1. 1579p 3189 3301p 1551 
2. 6319 8069p 8041 6431 
3. 20819 22429 22541p 20791 
4. 64039 65789p 65761p 64151p 
5. 193979p 195589 195701 193951p 
6. 583519p 585269p 585241 583631p 
7. 1752419p 1754029 1754141 1752391 
8. 5258839 5260589p 5260561p 5258951 
9. 15778379 15779989 15780101 15778351p 
10. 47336719 47338469 47338441p 47336831p 
11. 142012019p 142013629 142013741 142011991 
12. 426037639p 426039389p 426039361 426037751 
13. 1278114779 1278116389 1278116501p 1278114751p 
14. 3834345919 3834347669p 3834347641 3834346031 
15. 11503039619 11503041229p 11503041341 11503039591 
16. 34509120439 34509122189 34509122161 34509120551p 
17. 103527363179 103527364789p 103527364901 103527363151 
18. 310582091119 310582092869 310582092841 310582091231p 
19. 931746275219 931746276829p 931746276941 931746275191 
20. 2795238827239 2795238828989 2795238828961 2795238827351p 
21. 8385716483579p 8385716485189 8385716485301 8385716483551 
22. 25157149452319p 25157149454069 25157149454041 25157149452431p 
23. 75471448358819 75471448360429 75471448360541p 75471448358791 
24. 226414345078039p 226414345079789 226414345079761 226414345078151 
25. 679243035235979p 679243035237589p 679243035237701 679243035235951 
26. 2037729105709519 2037729105711269 2037729105711241p 2037729105709631 
27. 6113187317130419 6113187317132029p 6113187317132141 6113187317130391 
28. 18339561951392839 18339561951394589p 18339561951394561 18339561951392951 
29. 55018685854180379 55018685854181989 55018685854182101 55018685854180351p 
30. 165056057562542719p 165056057562544469 165056057562544441 165056057562542831p 
31. 495168172687630019p 495168172687631629 495168172687631741 495168172687629991 
32. 1485504518062891639p 1485504518062893389 1485504518062893361 1485504518062891751p 
33. 4456513554188676779 4456513554188678389 4456513554188678501 4456513554188676751p 
34. 13369540662566031919p 13369540662566033669 13369540662566033641 13369540662566032031 
35. 40108621987698097619p 40108621987698099229 40108621987698099341 40108621987698097591 
36. 120325865963094294439 120325865963094296189p 120325865963094296161 120325865963094294551 
37. 360977597889282885179 360977597889282886789 360977597889282886901p 360977597889282885151 
38. 1082932793667848657119 1082932793667848658869 1082932793667848658841p 1082932793667848657231 
39. 3248798381003545973219p 3248798381003545974829 3248798381003545974941 3248798381003545973191 

 
Also I found a ring with 32 layers that produces 57 primes:

 
1. 4951p 89p 1621p 1259p 
2. 6299p 6661p 2969p 7831 
3. 20791 15929 17461 17099p 
4. 53819p 54181p 50489 55351p 
5. 163351p 158489p 160021 159659 
6. 481499 481861p 478169p 483031p 
7. 1446391 1441529p 1443061 1442699 
8. 4330619 4330981 4327289 4332151p 
9. 12993751 12988889p 12990421p 12990059p 
10. 38972699p 38973061 38969369 38974231 
11. 116919991p 116915129 116916661 116916299p 
12. 350751419 350751781 350748089 350752951p 
13. 1052256151p 1052251289p 1052252821 1052252459p 
14. 3156759899p 3156760261p 3156756569p 3156761431 
15. 9470281591 9470276729 9470278261p 9470277899 
16. 28410836219 28410836581p 28410832889p 28410837751 
17. 85232510551 85232505689p 85232507221 85232506859 
18. 255697523099 255697523461 255697519769p 255697524631 
19. 767092571191 767092566329 767092567861p 767092567499 
20. 2301277705019p 2301277705381 2301277701689 2301277706551 
21. 6903833116951p 6903833112089p 6903833113621 6903833113259p 
22. 20711499342299 20711499342661p 20711499338969p 20711499343831p 
23. 62134498028791p 62134498023929 62134498025461 62134498025099 
24. 186403494077819 186403494078181 186403494074489 186403494079351p 
25. 559210482235351 559210482230489 559210482232021p 559210482231659 
26. 1677631446697499p 1677631446697861 1677631446694169 1677631446699031 
27. 5032894340094391p 5032894340089529 5032894340091061 5032894340090699 
28. 15098683020274619p 15098683020274981p 15098683020271289 15098683020276151p 
29. 45296049060825751 45296049060820889p 45296049060822421 45296049060822059p 
30. 135888147182468699 135888147182469061p 135888147182465369 135888147182470231 
31. 407664441547407991 407664441547403129p 407664441547404661 407664441547404299 
32. 1222993324642215419p 1222993324642215781 1222993324642212089 1222993324642216951 

 
Finally here is a ring with 6 layers where every number is prime:

 
1. 1091p 3001p 271p 257p 
2. 4349p 4363p 3529p 1619p 
3. 10331p 12241p 9511p 9497p 
4. 32069p 32083p 31249p 29339p 
5. 93491p 95401p 92671p 92657p 
6. 281549p 281563p 280729p 278819p 

 

***

Records   |  Conjectures  |  Problems  |  Puzzles