A352633 - OEIS

A352633

Lexicographically earliest sequence of distinct positive integers such for any n > 0, a(n) and a(n+1) are coprime and have no common 1-bits in their binary expansions.

%I #30 May 07 2022 15:29:14

%S 1,2,5,8,3,4,9,16,7,24,35,12,17,6,25,32,11,20,33,10,21,34,13,18,37,26,

%T 69,40,19,36,65,14,81,38,73,22,41,64,15,112,129,28,67,44,83,128,23,72,

%U 49,66,29,96,31,160,27,68,43,80,39,88,131,48,71,56,135,104

%N Lexicographically earliest sequence of distinct positive integers such for any n > 0, a(n) and a(n+1) are coprime and have no common 1-bits in their binary expansions.

%C This sequence combines features of A000027 (where two consecutive terms are coprime) and of A109812 (where two consecutive terms have no common 1-bits in their binary expansions).

%C For any n > 0, n and a(n) have the same parity.

%C The sequence is well defined:

%C - after an odd term v: we can extend the sequence with a power of 2 greater than any previous term,

%C - after an even term v < 2^k: we can extend the sequence with a prime number of the form 1 + t*2^k (Dirichlet's theorem on arithmetic progressions guarantees us that there is an infinity of such prime numbers).

%C This sequence is a permutation of the positive integers (with inverse A353604):

%C - the sequence is clearly unbounded,

%C - so we have even terms of infinitely many different binary lengths,

%C - the first even term with binary length w > 1 is necessarily 2^(w-1),

%C - so we have infinitely many powers of 2 in the sequence,

%C - so eventually all odd numbers will appear in the sequence,

%C - and all prime numbers will appear in the sequence,

%C - and eventually any even number v < 2^k must appear in the sequence (for instance after a prime number of the form 1 + t*2^k).

%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>

%e The first terms, alongside their binary expansion and distinct prime factors, are:

%e n a(n) bin(a(n)) dpf(a(n))

%e -- ---- --------- ----------

%e 1 1 1 None

%e 2 2 10 2

%e 3 5 101 5

%e 4 8 1000 2

%e 5 3 11 3

%e 6 4 100 2

%e 7 9 1001 3

%e 8 16 10000 2

%e 9 7 111 7

%e 10 24 11000 2 3

%e 11 35 100011 5 7

%e 12 12 1100 2 3

%e 13 17 10001 17

%e 14 6 110 2 3

%o (PARI) { s=0; v=1; for (n=1, 66, print1 (v", "); s+=2^v; for (w=1, oo, if (!bittest(s, w) && bitand(v,w)==0 && gcd(v,w)==1, v=w; break))) }

%Y Cf. A000027, A052531, A109812, inverse (A353604).

%K nonn,base

%O 1,2

%A _Rémy Sigrist_, May 07 2022