[mikalfpq] infinite collection of non-overlapping arithmetic sequences

start with 0, 1, 2,...

pick every other number, yielding the evens as the zeroth sequence.

of the remaining (i.e., odds), pick every other number, yielding 4*n+1 .

repeat with the remaining, yielding S[i][n] = (2^(i+1)) * n + (2^i-1) as the i-th sequence.

by construction, none of the sequences overlap.  every integer belongs to exactly one sequence.  by Dirichlet's theorem on arithmetic progressions, other than the evens, every sequence contains an infinite number of primes.  here are the first 20 primes for the first 20 sequences (giving the indices n which generate primes):

? S(i,n)=(2^(i+1)) * n + (2^i-1)
? for(i=1, +oo, print1(i":"); ct=0; for(n=0, +oo, if(ispseudoprime(S(i,n)), print1(" "n); ct+=1); if(ct>=20, print(); break)))

1: 1 3 4 7 9 10 13 15 18 22 24 25 27 28 34 37 39 43 45 48
2: 0 1 2 5 7 8 10 13 16 17 20 22 26 28 31 35 38 41 43 47
3: 0 1 4 6 9 10 12 16 19 22 27 30 31 37 39 40 45 46 51 52
4: 1 2 7 8 11 13 14 22 23 28 32 34 38 41 44 46 49 58 62 64
5: 0 3 7 9 13 15 22 24 27 28 30 33 34 37 40 42 49 52 64 69
6: 1 8 11 16 17 22 26 32 37 47 52 55 58 71 76 80 82 83 86 92
7: 0 1 4 6 10 15 21 24 27 34 36 39 46 49 51 55 69 70 76 90
8: 2 13 16 22 26 28 31 41 43 44 49 52 56 64 71 77 82 83 89 94
9: 3 12 22 24 25 30 33 34 43 45 48 52 54 64 67 69 87 90 97 100
10: 2 7 10 13 16 17 20 25 28 41 43 46 50 53 67 70 76 83 85 92
11: 1 12 15 31 34 36 40 42 49 51 57 61 66 70 76 79 82 84 90 91
12: 2 11 29 32 43 44 53 58 59 64 71 73 76 82 88 94 103 113 116 121
13: 0 4 10 15 24 30 34 45 57 67 70 72 88 105 118 144 153 162 184 189
14: 2 7 13 20 22 23 31 35 38 41 56 65 77 97 100 107 113 133 143 148
15: 4 22 24 27 39 45 46 61 66 69 72 82 96 99 117 136 157 160 172 187
16: 8 14 22 29 31 58 59 64 67 74 77 83 86 98 104 107 128 133 137 143
17: 0 3 7 12 30 34 40 45 84 90 93 100 103 118 120 132 133 145 150 153
18: 1 2 10 20 37 41 46 50 53 58 68 71 80 82 92 118 121 143 148 167
19: 0 25 30 34 36 37 45 46 49 51 57 66 69 76 99 106 111 114 120 132
20: 8 17 28 37 58 76 98 103 133 163 181 182 188 194 212 223 227 239 244 257

primes that occur at index n=0 are Mersenne primes.

the two argument function S[i][n] maps pairs of integers to single integers.  because each integer appears in exactly one sequence, the function has an inverse.  to invert, convert the input number into binary.  count the number of trailing set (1) bits, i.e., interpret the least significant bits as unary.  this yields i.  removing the trailing set bits and separator 0.  interpret the remaining upper bits as binary, yielding n.

the invertible mapping shows that the cardinality of the set of pairs of integers is the same as the cardinality of the set of integers (Cantor's aleph-null).

because the i coordinate is unary, things become unwieldy quickly.  we can improve things by mixing in some base 3 (ternary):

express a number i in binary.

start with the sequence S[n] = 0, 1, 2,...

run the following loop, examining the least significant bit of i.

if i has no bits left, form the new sequence S_new[n] = S_old[3*n] and exit, returning S_new as the i-th sequence.

if the LSB is 0, form the new sequence S_new[n] = S_old[3*n + 1] .

if the LSB is 1, form the new sequence S_new[n] = S_old[3*n + 2] .

set S_old := S_new and repeat with the next least significant bit of i.

S[i=0] is the multiples of 3.  every other sequence contains an infinite number of primes.

to invert, express a given integer in base 3.  examine the least significant digits up until the first 0.  map 1 and 2 to 0 and 1 respectively then interpret as binary, yielding i.  the remaining upper digits yield n (in ternary).  empty strings of digits encode the value zero.

future post ipwyvyeh, using base (2^256 + 230191).  it is important that the base be prime.