login
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.
1

%I #8 Jun 23 2022 08:11:36

%S 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,

%T 68,65,66,97,96,11,14,25,24,67,26,73,80,23,22,85,84,81,82,129,128,71,

%U 72,69,76,75,74,137,136,131,70,133,132,193,130,257,256,15,28

%N 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.

%C This sequence combines features of A065190 and of A238757.

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

%C This sequence is well defined:

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

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

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

%H Rémy Sigrist, <a href="/A355166/a355166.gp.txt">PARI program</a>

%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>

%e The first terms, alongside binary expansions and distinct prime factors, are:

%e n a(n) bin(n) bin(a(n)) dpf(n) dpf(a(n))

%e -- ---- ------ --------- ------ ---------

%e 1 2 1 10 {} {2}

%e 2 1 10 1 {2} {}

%e 3 4 11 100 {3} {2}

%e 4 3 100 11 {2} {3}

%e 5 8 101 1000 {5} {2}

%e 6 17 110 10001 {2, 3} {17}

%e 7 16 111 10000 {7} {2}

%e 8 5 1000 101 {2} {5}

%e 9 20 1001 10100 {3} {2, 5}

%e 10 21 1010 10101 {2, 5} {3, 7}

%o (PARI) See Links section.

%o (Python)

%o from math import gcd

%o from itertools import count, islice

%o def agen(): # generator of terms

%o aset, mink = set(), 1

%o for n in count(1):

%o an = mink

%o while an in aset or n&an or gcd(n, an)!=1: an += 1

%o aset.add(an); yield an

%o while mink in aset: mink += 1

%o print(list(islice(agen(), 65))) # _Michael S. Branicky_, Jun 22 2022

%Y Cf. A065190, A238757, A352633.

%K nonn,base

%O 1,1

%A _Rémy Sigrist_, Jun 22 2022