Problems & Puzzles: Puzzles

Puzzle 1059 Set of consecutive primes such that... JM Bergot sent the following puzzle: The following set of seven consecutive primes {5, 7, 11, 13, 17, 19, 23} is such that the sum of any two consecutive of them is divided by 3. Q. Can you find a larger set with this property?

---

During the week 16-22 October, 2021, contributions came from Fred Schneider, Paolo Lava, Ken Wilke, Shyam S. Gupta, Giorgos Kalogeropoulos, Simon Cavegn, Adam Stinchcombe, Osvar Volpatti, Emmanuel Vantieghem

***

Fred wrote:

Firstly, except for 2 and 3, all primes are of the form 6x + 1 or 6x + 5.
 

So, we need a chain of more than 7 primes such that consecutive primes alternate between 6a + 1 and 6b+ 5 or vice-versa..  That pairwise sum will be 6(a + b) and so a multiple of 3.

 

I found a list of 33 consecutive primes from 288413159 to 288413777 (Their mod 6 values are listed below.  You can see that they alternate between 5 and 1.  (

[(288413159,5),(288413173,1),(288413219,5),(288413233,1),(288413249,5),(288413263,1),(288413267,5),(288413269,1),(288413309,5),(288413329,1),(288413339,5),(288413383,1),(288413387,5),(288413413,1),(288413423,5),(288413443,1),(288413459,5),(288413467,1),(288413519,5),(288413581,1),(288413591,5),(288413611,1),(288413621,5),(288413659,1),(288413669,5),(288413683,1),(288413693,5),(288413707,1),(288413717,5),(288413743,1),(288413759,5),(288413773,1),(288413777,5)]

These were found with a brief Haskell program:
import Math.NumberTheory.Primes

import Data.List

f (x:y:xs) = (mod (x + y) 6):f(y:xs)

g ((x,y):xs) n = [x, y+1, n + y]:(g xs (n + y))
h q = g (map (\x -> (head x, length x)) $ group $ f $ take q $ drop 2 $ map unPrime primes) 3

filter (\x -> head x == 0 && (head $ tail x) >= 28) $ h 100000000

 

I found this number.   The last value is the index of the final prime in the sequence.
 

[0,33,15658033]

 

To get the prime list and the mod values, I ran this command:

map (\x -> (x, mod x 6)) $ take 33 $ drop (15658033-33) $ map unPrime primes

...

(Later he added)

I thought 33 might be the winner but I just found this one overnight: List of 34 primes between 62585146739 and 62585147419
 

 

***

Paolo wrote:

apparently, it appears an easy task (at least to the extent I searched for). These are the least sets of consecutive primes for n from 8 to 33:
 

n = 8 to 9 -> [89, 97, 101, 103, 107, 109, 113, 127, 131]

n = 10 to 21 -> [809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941]

n = 22 -> [3954889, 3954959, 3954961, 3954971, 3954997, 3955001, 3955009, 3955013, 3955027, 3955043, 3955069, 3955079, 3955087, 3955109, 3955117, 3955121, 3955123, 3955139, 3955141, 3955151, 3955153, 3955157]

n = 23 to 25  -> [15186319, 15186323, 15186331, 15186341, 15186349, 15186383, 15186397, 15186419, 15186433, 15186467, 15186469, 15186473, 15186481, 15186503, 15186511, 15186551, 15186553, 15186557, 15186571, 15186581, 15186583, 15186599, 15186607, 15186623, 15186631]

n = 26 to 28 -> [77011289, 77011303, 77011331, 77011369, 77011379, 77011447, 77011457, 77011477, 77011481, 77011507, 77011523, 77011537, 77011553, 77011573, 77011619, 77011621, 77011631, 77011639, 77011643, 77011651, 77011679, 77011681, 77011691, 77011747, 77011757, 77011777, 77011787, 77011801]

n = 29 to 33 -> [288413159, 288413173, 288413219, 288413233, 288413249, 288413263, 288413267, 288413269, 288413309, 288413329, 288413339, 288413383, 288413387, 288413413, 288413423, 288413443, 288413459, 288413467, 288413519, 288413581, 288413591, 288413611, 288413621, 288413659, 288413669, 288413683, 288413693, 288413707, 288413717, 288413743, 288413759, 288413773, 288413777]

 

***

Ken wrote:

Attached is a comment on Problem 1059. Thanks for an interesting bit of eyestrain.

Since all primes p > 3 are of the form 6k+1 or 6k-1, 3 in the statement of the problem can
be replaced by 6. Furthermore, looking at a table of primes for a desired sequence, the
search stops when two consecutive primes differ by a multiple of 6. Also the difference d
between consecutive primes of a desired sequence must satisfy d == 2 (mod 6) or d == 4
(mod 6) with consecutive differences alternating between the possible values of d.
Using these observations, a visual check of a tale of primes, 1000 yields the following
sequences:
97, 101, 103, 107, 109, 113, 127 and 131 of length 8,
389, 397, 401, 409, 419, 421, 431 and 433 of length 8,
277, 281, 283, 293, 307, 311, 313, 317, and 331 of length 9 and the surprising sequence
809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911,
919, 929, 937 and 941 of length 21.
At this point the eyestrain was too much.

***

Shyam wrote:

Solution:

There are number of larger sets. On investigating primes up to 10^11, it is found that the smallest
set of thirty three (33) consecutive primes such that the sum of any two consecutive of them is divided
by 3 is.
{288413159, 288413173, 288413219, 288413233, 288413249, 288413263, 288413267, 288413269, 288413309,
288413329, 288413339, 288413383, 288413387, 288413413, 288413423, 288413443, 288413459, 288413467,
288413519, 288413581, 288413591, 288413611, 288413621, 288413659, 288413669, 288413683, 288413693,
288413707, 288413717, 288413743, 288413759, 288413773, 288413777}

The following is the smallest set of thirty four (34) consecutive primes such that the sum of any two
consecutive of them is divided by 3.
{62585146739, 62585146759, 62585146769, 62585146777, 62585146781, 62585146783, 62585146787,
62585146837, 62585146847, 62585146891, 62585146931,62585146951, 62585147003, 62585147089, 62585147099,
62585147113, 62585147117, 62585147161, 62585147171, 62585147197, 62585147201, 62585147221, 62585147249,
62585147269, 62585147309, 62585147311, 62585147321, 62585147347, 62585147357, 62585147371, 62585147381,
62585147389, 62585147411, 62585147419}
This is no set of more than 34 such consecutive primes below 10^11.

***

Giorgos wrote:

Here is a set of 38 consecutive primes

{143014298809,143014298831,143014298851,143014298879,143014298887,143014298891,143014298893,
143014298927,143014298941,143014298963,143014298983,143014298993,143014299007,143014299017,
143014299031,143014299107,143014299133,143014299143,143014299187,143014299203,143014299217,
143014299293,143014299319,143014299347,143014299367,143014299383,143014299403,143014299419,
143014299427,143014299473,143014299481,143014299497,143014299511,143014299521,143014299523,
143014299599,143014299601,143014299611}

***

Simon wrote:

7: 5, 7, 11, 13, 17, 19, 23
9: 89, 97, 101, 103, 107, 109, 113, 127, 131
21: 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941
22: 3954889, 3954959, 3954961, 3954971, 3954997, 3955001, 3955009, 3955013, 3955027, 3955043, 3955069, 3955079, 3955087, 3955109, 3955117, 3955121, 3955123, 3955139, 3955141, 3955151, 3955153, 3955157
25: 15186319, 15186323, 15186331, 15186341, 15186349, 15186383, 15186397, 15186419, 15186433, 15186467, 15186469, 15186473, 15186481, 15186503, 15186511, 15186551, 15186553, 15186557, 15186571, 15186581, 15186583, 15186599, 15186607, 15186623, 15186631
28: 77011289, 77011303, 77011331, 77011369, 77011379, 77011447, 77011457, 77011477, 77011481, 77011507, 77011523, 77011537, 77011553, 77011573, 77011619, 77011621, 77011631, 77011639, 77011643, 77011651, 77011679, 77011681, 77011691, 77011747, 77011757, 77011777, 77011787, 77011801
33: 288413159, 288413173, 288413219, 288413233, 288413249, 288413263, 288413267, 288413269, 288413309, 288413329, 288413339, 288413383, 288413387, 288413413, 288413423, 288413443, 288413459, 288413467, 288413519, 288413581, 288413591, 288413611, 288413621, 288413659, 288413669, 288413683, 288413693, 288413707, 288413717, 288413743, 288413759, 288413773, 288413777
34: 62585146739, 62585146759, 62585146769, 62585146777, 62585146781, 62585146783, 62585146787, 62585146837, 62585146847, 62585146891, 62585146931, 62585146951, 62585147003, 62585147089, 62585147099, 62585147113, 62585147117, 62585147161, 62585147171, 62585147197, 62585147201, 62585147221, 62585147249, 62585147269, 62585147309, 62585147311, 62585147321, 62585147347, 62585147357, 62585147371, 62585147381, 62585147389, 62585147411, 62585147419
35: 114058236679, 114058236827, 114058236829, 114058236863, 114058236907, 114058236959, 114058236973, 114058236989, 114058236991, 114058237001, 114058237021, 114058237043, 114058237057, 114058237079, 114058237099, 114058237127, 114058237129, 114058237151, 114058237171, 114058237217, 114058237219, 114058237247, 114058237291, 114058237301, 114058237351, 114058237367, 114058237399, 114058237427, 114058237453, 114058237463, 114058237483, 114058237499, 114058237507, 114058237511, 114058237519
38: 143014298809, 143014298831, 143014298851, 143014298879, 143014298887, 143014298891, 143014298893, 143014298927, 143014298941, 143014298963, 143014298983, 143014298993, 143014299007, 143014299017, 143014299031, 143014299107, 143014299133, 143014299143, 143014299187, 143014299203, 143014299217, 143014299293, 143014299319, 143014299347, 143014299367, 143014299383, 143014299403, 143014299419, 143014299427, 143014299473, 143014299481, 143014299497, 143014299511, 143014299521, 143014299523, 143014299599, 143014299601, 143014299611
39: 2320700383121, 2320700383237, 2320700383241, 2320700383273, 2320700383307, 2320700383357, 2320700383427, 2320700383429, 2320700383439, 2320700383447, 2320700383487, 2320700383537, 2320700383541, 2320700383579, 2320700383583, 2320700383591, 2320700383619, 2320700383657, 2320700383679, 2320700383711, 2320700383739, 2320700383747, 2320700383763, 2320700383819, 2320700383853, 2320700383909, 2320700383919, 2320700383927, 2320700383961, 2320700383993, 2320700383997, 2320700384029, 2320700384069, 2320700384071, 2320700384129, 2320700384131, 2320700384141, 2320700384179, 2320700384183
41: 2942277160583, 2942277160609, 2942277160637, 2942277160687, 2942277160703, 2942277160759, 2942277160769, 2942277160807, 2942277160829, 2942277160831, 2942277160847, 2942277160951, 2942277160961, 2942277160993, 2942277161009, 2942277161041, 2942277161069, 2942277161071, 2942277161111, 2942277161113, 2942277161171, 2942277161179, 2942277161189, 2942277161233, 2942277161297, 2942277161323, 2942277161339, 2942277161371, 2942277161387, 2942277161389, 2942277161423, 2942277161443, 2942277161489, 2942277161497, 2942277161591, 2942277161599, 2942277161633, 2942277161647, 2942277161651, 2942277161671, 2942277161687
42: 4386778243843, 4386778243871, 4386778243921, 4386778243943, 4386778244029, 4386778244039, 4386778244047, 4386778244081, 4386778244089, 4386778244099, 4386778244197, 4386778244213, 4386778244221, 4386778244231, 4386778244239, 4386778244249, 4386778244269, 4386778244339, 4386778244341, 4386778244363, 4386778244383, 4386778244417, 4386778244449, 4386778244477, 4386778244491, 4386778244501, 4386778244521, 4386778244531, 4386778244551, 4386778244603, 4386778244647, 4386778244687, 4386778244713, 4386778244729, 4386778244731, 4386778244741, 4386778244743, 4386778244801, 4386778244803, 4386778244843, 4386778244857, 4386778244867
43: 16104860854333, 16104860854337, 16104860854393, 16104860854457, 16104860854507, 16104860854547, 16104860854609, 16104860854613, 16104860854699, 16104860854721, 16104860854729, 16104860854739, 16104860854741, 16104860854751, 16104860854777, 16104860854811, 16104860854879, 16104860854913, 16104860854921, 16104860854961, 16104860854963, 16104860854967, 16104860854981, 16104860854991, 16104860855059, 16104860855093, 16104860855101, 16104860855141, 16104860855191, 16104860855207, 16104860855233, 16104860855261, 16104860855329, 16104860855333, 16104860855341, 16104860855387, 16104860855401, 16104860855483, 16104860855497, 16104860855513, 16104860855527, 16104860855549, 16104860855557
48: 23171469790747, 23171469790787, 23171469790789, 23171469790811, 23171469790813, 23171469790817, 23171469790849, 23171469790853, 23171469790873, 23171469790883, 23171469790891, 23171469790943, 23171469790957, 23171469791009, 23171469791023, 23171469791033, 23171469791047, 23171469791051, 23171469791053, 23171469791123, 23171469791131, 23171469791159, 23171469791161, 23171469791201, 23171469791203, 23171469791219, 23171469791221, 23171469791231, 23171469791263, 23171469791333, 23171469791389, 23171469791411, 23171469791467, 23171469791501, 23171469791527, 23171469791531, 23171469791557, 23171469791579, 23171469791647, 23171469791693, 23171469791713, 23171469791783, 23171469791893, 23171469791933, 23171469791971, 23171469791999, 23171469792103, 23171469792131

***

Adam wrote:

The largest I found so far is length 33, starting at 288413159.  This is consistent with the idea that the primes (except 2,3) are a random string of +1/-1 mod 6 so you would expect to search 2^n terms to find a specified length-n string of +1 and -1.  The 2^n -th prime is around 2^n/(log(2^n) and the ratio between that and the actual appearance p=288413159 for n=33 is about 1.3 which I would call "one-ish."  Nothing longer through 8670153491.

***

 

Oscar wrote:

A set of n = 9 consecutive primes starts from p = 89:
{89, 97, 101, 103, 107, 109, 113, 127, 131}
then a larger set of n = 21 consecutive primes starts from p = 809: 
{809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941}

After these lucky results, finding larger sets requires choosing much larger starting primes. 
First 15 champions (set size vs starting prime):
7  5
9  89
21  809
22  3954889
25  15186319
28  77011289
33  288413159
34  62585146739
35  114058236679
38  143014298809
39  2320700383121
41  2942277160583
42  4386778243843
43  16104860854333
48  23171469790747

***

Emmanuel wrote:

I found a set of  32  consecutive primes with the desired property :

 

 {288413173, 288413219, 288413233, 288413249, 288413263, 288413267, 288413269, 288413309, 288413329, 288413339, 288413383, 288413387, 288413413, 288413423, 288413443, 288413459, 288413467, 288413519, 288413581, 288413591, 288413611, 288413621, 288413659, 288413669, 288413683, 288413693, 288413707, 288413717, 288413743, 288413759, 288413773, 288413777}
 

There might exist bigger such sets, but only when the first prime is > 17*10^9.

***

On Oct 22, 2021, Alexander Violette wrote:

I went program-free for this problem to see how viable it is and I found 5 sets of consecutive primes larger than the one mentioned in the problem. 2 have 9 primes and 3 have 10. I looked at primes p where p, p+2, p+6, and p+8 are all primes as those were 4 free primes towards the problem. Granted, I can imagine larger sets not having this subset but I was unable to find any quickly looking through prime lists. An even better approach would be looking at prime sextuples or some larger sets of consecutive primes where none of the prime gaps are divisible by 3.
 

l=9

{89, 97, 101, 103, 107, 109, 113, 127, 131}
 

{9419, 9421, 9431, 9433, 9437, 9439, 9461, 9463, 9467}

l=10

{809, 811, 821, 823, 827, 829, 839, 853, 857, 859}

{3413, 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499}

{15667, 15671, 15679, 15683, 15727, 15731, 15733, 15737, 15739, 15749}

...

I also found this set of 17 consecutive primes:
{43777, 43781, 43783, 43787, 43789, 43793, 43801, 43853, 43867, 43889, 43891, 43913, 43933, 43943, 43951, 43961, 43963}