Problems & Puzzles: Puzzles

Puzzle 448. p+q not divided by 3 J. M. Bergot sent the following puzzle: Find large runs of consecutive primes such that the sum of every two adjacent primes is not divided by 3. Carlos Rivera found a run of 17 of these primes starting at 232301497. Q1. Find larger runs of these. Q2 Find runs of consecutive primes such that sum of every two primes in the run is not divided by 3.

---

Farideh Firoozbakht & J. K. Andersen contributed.

***

Farideh wrote:

It's obvious that all primes of each such chain are congruent mod 3.
So I think Q1=Q2.

Please see the following two sequences.

1. A055625 : First prime starting a chain of exactly n consecutive primes congruent to 1 mod 6.

7, 31, 151, 3049, 7351, 1741, 19471, 118801, 498259, 148531, 406951, 2513803, 2339041, 89089369, 51662593, 73451737, 232301497, 450988159, 1558562197, 2506152301, 1444257673, 28265029657, 24061965043, 87996684091, 43553959717.

2. A055626 : First prime starting a chain of exactly n consecutive primes congruent to 5 mod 6

5, 23, 47, 251, 1889, 7793, 43451, 243161, 726893, 759821, 2280857, 1820111, 10141499, 40727657, 19725473, 136209239, 744771077, 400414121, 1057859471, 489144599, 13160911739, 766319189, 38451670931, 119618704427, 21549657539.

So A055625(k) for k>17 & A055626(k) for k>17 are solutions for both Q1 & Q2. Also length of the chain starting at p=A055626(25)=21549657539 is 25 and p is the smallest prime such that the corresponding chain has length 25 and maybe Jens Kruse Andersen or Herman Jamke can find chains of primes with larger lengths.

***

Andersen wrote:

Q1 and Q2.
Primes above 3 are either of form 6n-1 or 6n+1. If 2 primes are of different forms then their sum is divisible by 3. So for both questions we want many consecutive primes with the same value modulo 6. The start of the first run of each length is at http://hjem.get2net.dk/jka/math/congruent-primes.htm#mod6
The longest runs below 10^13 are of length 31, starting at 1552841185921 for 6n+1 and at 5611314737339 for 6n-1. As the link shows, it's easier to find consecutive primes where the sum of every two adjacent primes IS divisible by 3. A run of 38 starts at 143014298809.

***