cp's OEIS Frontend

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 A352633 #30 May 07 2022 15:29:14
%S A352633 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 A352633 69,40,19,36,65,14,81,38,73,22,41,64,15,112,129,28,67,44,83,128,23,72,
%U A352633 49,66,29,96,31,160,27,68,43,80,39,88,131,48,71,56,135,104
%N 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.
%C A352633 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 A352633 For any n > 0, n and a(n) have the same parity.
%C A352633 The sequence is well defined:
%C A352633 - after an odd term v: we can extend the sequence with a power of 2 greater than any previous term,
%C A352633 - 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 A352633 This sequence is a permutation of the positive integers (with inverse A353604):
%C A352633 - the sequence is clearly unbounded,
%C A352633 - so we have even terms of infinitely many different binary lengths,
%C A352633 - the first even term with binary length w > 1 is necessarily 2^(w-1),
%C A352633 - so we have infinitely many powers of 2 in the sequence,
%C A352633 - so eventually all odd numbers will appear in the sequence,
%C A352633 - and all prime numbers will appear in the sequence,
%C A352633 - 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 A352633 <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%e A352633 The first terms, alongside their binary expansion and distinct prime factors, are:
%e A352633   n   a(n)  bin(a(n))  dpf(a(n))
%e A352633   --  ----  ---------  ----------
%e A352633    1     1          1  None
%e A352633    2     2         10  2
%e A352633    3     5        101      5
%e A352633    4     8       1000  2
%e A352633    5     3         11    3
%e A352633    6     4        100  2
%e A352633    7     9       1001    3
%e A352633    8    16      10000  2
%e A352633    9     7        111        7
%e A352633   10    24      11000  2 3
%e A352633   11    35     100011      5 7
%e A352633   12    12       1100  2 3
%e A352633   13    17      10001          17
%e A352633   14     6        110  2 3
%o A352633 (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 A352633 Cf. A000027, A052531, A109812, inverse (A353604).
%K A352633 nonn,base
%O A352633 1,2
%A A352633 _Rémy Sigrist_, May 07 2022