Problems & Puzzles: Puzzles

Puzzle 1179  A sequence by Polo Lava Paolo Lava sent the following puzzle: Consider a sequence a(n) set according to the following rules: a) a(1) = 1. b) The number a(n) says that after a(n) positions we have a prime that is the least prime not yet present in the sequence. c) Positions not occupied by primes are filled with the least composite non yet present in the sequence.   Here below the first 100 elements of the sequence: n a(n) 1 1 2 2 3 4 4 3 5 6 6 8 7 5 8 9 9 10 10 12 11 7 12 11 13 14 14 13 15 15 16 16 17 17 18 19 19 23 20 18 21 20 22 29 23 31 24 21 25 22 26 24 27 37 28 25 29 26 30 41 31 27 32 43 33 28 34 47 35 30 36 32 37 53 38 59 39 33 40 34 41 61 42 67 43 35 44 36 45 71 46 38 47 73 48 39 49 40 50 79 51 83 52 42 53 89 54 97 55 101 56 44 57 45 58 103 59 46 60 48 61 107 62 49 63 50 64 109 65 113 66 51 67 52 68 127 69 54 70 55 71 131 72 137 73 56 74 139 75 149 76 57 77 58 78 151 79 60 80 157 81 163 82 62 83 63 84 167 85 64 86 65 87 173 88 66 89 179 90 181 91 68 92 69 93 70 94 191 95 72 96 74 97 193 98 75 99 76 100 197   I will try to explain the process: a(1) = 1 so a(1+1) = a(2) must be a prime that, being the first one, is 2 -> a(2) = 2. Now, a(2+2) = a(4) must be a prime and the least one not yet present is 3 -> a(4) = 3. We need to fill a(3): here the position is not occupied by a prime and therefore the least composite not yet present is 4 -> a(3) = 4. Now this implies that a(3+4) = a(7) must be a prime. Note that being a(4) = 3 it leads to the same occurrence: a(4+3) = a(7) must be a prime. The least prime not yet present is 5 -> a(7) = 5. We need to fill a(5) and a(6) with composites -> a(5) = 6 and a(6) = 8. Again, a(5+6) = a(11), a(6+8) = a(14) and a(7+5) = a(12) must be primes. Starting from a(11) we have: a(11) = 7, a(12) = 11 and a(14) = 13. We need to fill a(8), a(9), a(10), a(13) with composites -> a(8) = 9, a(9) = 10, a(10) = 12, a(13) = 14. Now, it'd be clear that a(8+9) = a(17), a(11+7) = a(18), a(9+10) = a(19), a(10+12) = a(22), a(12+11) = a(23), a(13+14) = a(27) must be primes. And so on ... Given that the prime numbers are getting closer to each other, the graph of values tends to diverge more and more:   Questions   1) In the first 100 terms primes that are in prime positions (n=prime) are 2,5,7,17,23,31,53,61,73,89,107,131,179,193 (positions n=2,7,11,17,19,23,37,41,47,53,61,71,89,97). Can you extend the list? 2) The least consecutive two primes are (7, 11), three primes (17,19, 23). Which are the least consecutive four, five, six, etc. primes? 3) Same question as 2) but for composites: least consecutive two composites are (6, 8), three composites (9, 10, 12). Which are the least consecutive four, five, six, etc. composites?

---

From July 6 to July 13, contributions came from Michael Branicky, Giorgos Kalogeropoulos, Emmanuel Vantieghem, Oscar Volpatti

***

Michael wrote:

I computed a(n) up to n = 660,000,000.  At that point, there were 13,619,179 primes in prime positions.

There were no runs of consecutive primes with length >= 4 found.

The least runs of consecutive composites of lengths 4 and 5 are:
 

    Length 4:  (142, 143, 144, 145);

    Length 5:  (1119, 1120, 1121, 1122, 1124).

 

***

Giorgos wrote:

This sequence is A249054 first published by N. J. A. Sloane, Nov 01 2014

I computed the first 10^8 terms and here are my results:

 

Q1) Here are the first 100 primes in prime positions

2,5,7,17,23,31,53,61,73,89,107,131,179,193,227,233,293,317,331,359,367,383,401,439,463,499,521,557,587,
619,631,647,659,761,809,859,887,967,1031,1049,1087,1117,1129,1153,1201,1223,1289,1297,1303,1327,1409,
1447,1453,1487,1523,1531,1579,1597,1607,1657,1753,1811,2027,2081,2311,2341,2371,2393,2411,2437,2473,
2503,2663,2711,2741,2753,2801,2803,2953,2971,3001,3061,3089,3163,3271,3301,3469,3533,3583,3733,3853,
3911,3923,4127,4139,4159,4217,4283,4409,4447... 
 

and the first 100 positions are

2,7,11,17,19,23,37,41,47,53,61,71,89,97,109,113,139,149,151,163,167,173,181,197,211,223,229,239,251,269,
271,277,283,317,331,347,359,379,401,409,421,439,443,449,461,467,491,499,503,509,523,541,547,557,569,571,
587,593,601,613,643,661,727,743,823,829,839,853,857,863,877,881,919,937,947,953,967,971,1009,1019,1021,
1039,1049,1063,1103,1109,1163,1181,1201,1249,1283,1297,1303,1361,1367,1373,1381,1409,1439,1451...
 

These sequences can be easily extended.

 

Q2) In the first 10^8 terms, no 4 consecutive primes were found.

 

Q3) 4 composites: 142, 143, 144, 145

       5 composites: 1119, 1120, 1121, 1122, 1124

***

Emmanuel wrote:

It looks like Paolo's sequence is  A249054  at the OEIS.
Using the first  10000  elements from the b-file we can answer Q1
I. e. : the primes on a prime place are  2,7,11,17,19,23,37,41,47,53,61,71,89,97,109,113,139,149,151,163,167,
173,181,197,211,223,229,239,251,269,271,277,283,317,331,347,359,379,401,409,421,439,443,449,461,467,491,
499,503,509,523,541,547,557,569,571,587,593,601,613,643,661,727,743,823,829,839,853,857,863,877,881,
919,937,947,953,967,971,1009,1019,1021,1039,1049,1063,1103,1109,1163,1181,1201,1249,1283,1297,1303,
1361,1367,1373,1381,1409,1439,1451,1481,1487,1543,1553,1559,1583,1597,1607,1619,1621,1637,1667,1699,
1733,1741,1759,1777,1831,1861,1867,1871,1873,1913,1949,1973,1979,2039,2053,2063,2083,2089,2099,2131,
2137,2153,2161,2179,2237,2243,2293,2297,2311,2339,2357,2377,2381,2389,2423,2459,2467,2473,2477,2503,
2543,2551,2557,2579,2593,2609,2621,2647,2663,2671,2677,2687,2689,2699,2711,2713,2731,2767,2797,2801,
2803,2819,2837,2843,2857,2861,2897,2909,2927,2957,2969,2971,2999,3001,3011,3019,3023,3041,3061,3083,
3089,3109,3121,3137,3167,3169,3251,3259,3301,3319,3329,3343,3361,3371,3373,3391,3407,3433,3449,3457,
3461,3463,3469,3491,3499,3511,3517,3529,3533,3547,3571,3583,3593,3607,3613,3617,3643,3677,3709,3733,
3767,3793,3823,3863,3881,3907,3911,3917,3919,3923,3931,3947,4001,4007,4013,4019,4051,4073,4111,4133,
4159,4177,4219,4253,4271,4297,4337,4339,4423,4457,4493,4513,4519,4549,4603,4637,4639,4643,4651,4657,
4663,4679,4703,4721,4729,4751,4787,4793,4813,4861,4871,4903,4909,4931,4933,4937,4973,4999,5009,5011,
5021,5059,5077,5087,5101,5119,5147,5179,5189,5209,5233,5261,5273,5303,5347,5387,5393,5399,5413,5419,
5431,5437,5441,5449,5471,5507,5519,5521,5527,5531,5573,5639,5641,5653,5659,5693,5701,5737,5743,5783,
5791,5807,5839,5849,5851,5869,5879,5953,5981,6007,6037,6053,6067,6091,6101,6121,6131,6143,6151,6203,
6211,6221,6229,6263,6269,6271,6311,6329,6359,6361,6367,6373,6379,6389,6421,6481,6491,6521,6563,6569,
6599,6637,6653,6659,6673,6679,6691,6701,6763,6781,6793,6803,6827,6829,6863,6883,6911,6917,6947,6949,
6959,6961,6971,6977,6997,7043,7079,7103,7109,7151,7177,7187,7211,7213,7243,7349,7351,7369,7411,7451,
7459,7477,7487,7489,7499,7507,7523,7529,7559,7561,7583,7681,7723,7727,7741,7757,7817,7841,7907,7937,
7949,7963,7993,8009,8039,8053,8093,8123,8171,8221,8233,8269,8297,8329,8363,8419,8429,8443,8461,8521,
8537,8539,8573,8581,8669,8677,8693,8699,8731,8737,8779,8783,8803,8807,8819,8821,8861,8933,8999,9001,
9011,9043,9067,9137,9151,9157,9203,9227,9239,9257,9283,9311,9319,9337,9349,9371,9377,9391,9403,9421,
9437,9467,9491,9497,9511,9533,9547,9601,9613,9623,9677,9679,9719,9721,9739,9749,9767,9769,9781,9787,
9817,9839,9857,9871,9883,9887,9901,9931,9973.
About Q2 : I found no more than three consecutive primes
About Q3 ; the first duo starts at position 7 : {6, 8}
the first trio starts at position 11 : {9, 10, 12}
the first quartet starts at position 194 : {142, 143, 144, 145}
the first quintet starts at position 1597, "  ", {1119, 1120, 1121, 1122, 1124}.

Perhaps there might be more interesting results if we could ectand the b-file of  A249054.

***

Oscar wrote:

Sequence a(n) contains no four consecutive primes and no six consecutive composites.

According to Paolo Lava's process, related sequence b(n) = n+a(n) provides all positions j such that a(j) will be prime:

2, 4, 7, 7, 11, 14, 12, 17, 19, 22, 18, 23, 27, 27, ...

Sequence b(n) is unsorted and contains repetitions; let's sort it and remove duplicate positions, obtaining strictly increasing sequence x(k):

2, 4, 7, 11, 12, 14, 17, 18, 19, 22, 23, 27, ...

Similarly define strictly increasing sequence y(k), which provides all positions j such that a(j) will be composite:

3, 5, 6, 8, 9, 10, 13, 15, 16, 20, 21, 24, 25, 26, ...

 

If we put n=x(k) within sequence b(n), we obtain subsequence sx(k) = x(k)+prime(k), strictly increasing:  

4, 7, 12, 18, 23, 27, ...

If we put n=y(k) within sequence b(n), we obtain subsequence sy(k) = y(k)+composite(k), strictly increasing: 
 

7, 11, 14, 17, 19, 22, 27, ...

Hence, the union of sx(k) and sy(k) provides every position j>2 such that a(j) will be prime. 
 

Assume that sequence a(n) contains a prime in four consecutive positions n,...,n+3.

All such target positions must belong either to sx(k), or to sy(k), or to both. But this can never happen.

Difference sy(k+1)-sy(k) is at least 2:
 

both y(k) and composite(k) will increase by at least one unit from k to k+1.

Difference sx(k+1)-sx(k) is at least 3:

for k=1, equality sx(2)-sx(1)=7-4=3 holds;

for k>1, all primes after prime(1)=2 are odd, hence prime(k) will increase by at least two units from k to k+1.

At most two target positions can simultaneously belong to sy(k):
 

n and n+2, or n and n+3, or n+1 and n+3.

In each case, the distance between remaining positions is at most 2, so they can't both belong to sx(k). 

Difference sy(k+1)-sy(k) is at most 6, so there can be no six consecutive composites.
 

From k to k+1:

y(k) will increase by at most 4, if y(k)+1,...,y(k)+3 are three consecutive positions filled by primes;

composite(k) will increase by at most 2, if composite(k)+1 is an odd prime (there are no more consecutive primes after composite(1) = 4).

 

***