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

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.

Links

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

Rémy Sigrist, PARI program

Index entries for sequences that are permutations of the natural numbers

Example

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}

Prog

(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

Crossrefs

Cf. A065190, A238757, A352633.

Sequence in context: A306888 A262230 A262155 * A181882 A109195 A258310

Adjacent sequences: A355163 A355164 A355165 * A355167 A355168 A355169

Keyword

nonn,base

Author

Rémy Sigrist, Jun 22 2022

Status

approved