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.

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, 69, 40, 19, 36, 65, 14, 81, 38, 73, 22, 41, 64, 15, 112, 129, 28, 67, 44, 83, 128, 23, 72, 49, 66, 29, 96, 31, 160, 27, 68, 43, 80, 39, 88, 131, 48, 71, 56, 135, 104

Offset: 1

Author

Rémy Sigrist, May 07 2022

Keywords

• nonn
• base

Comments

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).

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

The sequence is well defined:

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

- 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).

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

- the sequence is clearly unbounded,

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

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

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

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

- and all prime numbers will appear in the sequence,

- 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).

Examples

			The first terms, alongside their binary expansion and distinct prime factors, are:
  n   a(n)  bin(a(n))  dpf(a(n))
  --  ----  ---------  ----------
   1     1          1  None
   2     2         10  2
   3     5        101      5
   4     8       1000  2
   5     3         11    3
   6     4        100  2
   7     9       1001    3
   8    16      10000  2
   9     7        111        7
  10    24      11000  2 3
  11    35     100011      5 7
  12    12       1100  2 3
  13    17      10001          17
  14     6        110  2 3
		

Links

• Index entries for sequences that are permutations of the natural numbers

Crossrefs

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

Programs

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))) }