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

2, 1, 4, 3, 8, 17, 16, 5, 20, 21, 32, 19, 18, 33, 64, 7, 6, 13, 12, 9, 10, 41, 40, 35, 34, 37, 68, 65, 66, 97, 96, 11, 14, 25, 24, 67, 26, 73, 80, 23, 22, 85, 84, 81, 82, 129, 128, 71, 72, 69, 76, 75, 74, 137, 136, 131, 70, 133, 132, 193, 130, 257, 256, 15, 28

Offset: 1

Author

Rémy Sigrist, Jun 22 2022

Keywords

• nonn
• base

Comments

This sequence combines features of A065190 and of A238757.

This sequence is a self-inverse permutation of the nonnegative integers, without fixed points.

This sequence is well defined:

- if n is odd, then we can extend the sequence with a power of 2 > n,

- if n < 2^k is even, then 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).

When n is odd, a(n) is even and vice-versa.

Examples

			The first terms, alongside binary expansions and distinct prime factors, are:
  n   a(n)  bin(n)  bin(a(n))  dpf(n)  dpf(a(n))
  --  ----  ------  ---------  ------  ---------
   1     2       1         10  {}      {2}
   2     1      10          1  {2}     {}
   3     4      11        100  {3}     {2}
   4     3     100         11  {2}     {3}
   5     8     101       1000  {5}     {2}
   6    17     110      10001  {2, 3}  {17}
   7    16     111      10000  {7}     {2}
   8     5    1000        101  {2}     {5}
   9    20    1001      10100  {3}     {2, 5}
  10    21    1010      10101  {2, 5}  {3, 7}
		

Links

• Rémy Sigrist, PARI program
• Index entries for sequences that are permutations of the natural numbers

Crossrefs

Cf. A065190, A238757, A352633.

Programs

PARI

See Links section.

Python

from math import gcd
from itertools import count, islice
def agen(): # generator of terms
    aset, mink = set(), 1
    for n in count(1):
        an = mink
        while an in aset or n&an or gcd(n, an)!=1: an += 1
        aset.add(an); yield an
        while mink in aset: mink += 1
print(list(islice(agen(), 65))) # Michael S. Branicky, Jun 22 2022