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,2

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

Links

Table of n, a(n) for n=1..66.

Index entries for sequences that are permutations of the natural numbers

Example

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

Prog

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

Crossrefs

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

Sequence in context: A198545 A296430 A220398 * A200225 A258749 A056886

Adjacent sequences: A352630 A352631 A352632 * A352634 A352635 A352636

Keyword

nonn,base

Author

Rémy Sigrist, May 07 2022

Status

approved