cp's OEIS Frontend

A354182 Lexicographically earliest sequence of distinct nonnegative integers such that for any n >= 0, the binary expansions of n and n + a(n) have no 1's in common.

%I A354182 #13 Jul 14 2024 10:56:47
%S A354182 0,1,2,5,4,3,10,9,8,7,6,21,20,19,18,17,16,15,14,13,12,11,42,41,40,39,
%T A354182 38,37,36,35,34,33,32,31,30,29,28,27,26,25,24,23,22,85,84,83,82,81,80,
%U A354182 79,78,77,76,75,74,73,72,71,70,69,68,67,66,65,64,63,62,61
%N A354182 Lexicographically earliest sequence of distinct nonnegative integers such that for any n >= 0, the binary expansions of n and n + a(n) have no 1's in common.
%C A354182 This sequence is a self-inverse permutation of the nonnegative integers.
%C A354182 This sequence has similarities with A065190; here n and n + a(n) have no 1's in common, there they have no common prime factor.
%C A354182 Empirically:
%C A354182 - for n > 0, b(n) = n + a(n) is always a power of 2,
%C A354182 - 2^k appears A001045(k) times in sequence b.
%H A354182 Robert Israel, <a href="/A354182/b354182.txt">Table of n, a(n) for n = 0..10000</a>
%H A354182 <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%e A354182 The first terms, alongside the binary expansions of n and n + a(n), are:
%e A354182   n   a(n)  bin(n)  bin(n+a(n))
%e A354182   --  ----  ------  -----------
%e A354182    0     0       0            0
%e A354182    1     1       1           10
%e A354182    2     2      10          100
%e A354182    3     5      11         1000
%e A354182    4     4     100         1000
%e A354182    5     3     101         1000
%e A354182    6    10     110        10000
%e A354182    7     9     111        10000
%e A354182    8     8    1000        10000
%e A354182    9     7    1001        10000
%e A354182   10     6    1010        10000
%e A354182   11    21    1011       100000
%e A354182   12    20    1100       100000
%e A354182   13    19    1101       100000
%e A354182   14    18    1110       100000
%e A354182   15    17    1111       100000
%e A354182   16    16   10000       100000
%p A354182 S:= [$0..100]: R:= NULL:
%p A354182 for n from 0 do
%p A354182   L:= convert(n,base,2); d:= nops(L);
%p A354182   found:= false;
%p A354182   for i from 1 to nops(S) do
%p A354182     x:= S[i];
%p A354182     Lx:= convert(n+x,base,2); dx:= nops(Lx);
%p A354182     if andmap(t -> Lx[t]=0 or L[t] = 0, [$1..min(d,dx)]) then
%p A354182       found:= true; R:= R,x; S:=subsop(i=NULL,S); break
%p A354182     fi
%p A354182   od;
%p A354182   if not found then break fi
%p A354182 od:
%p A354182 R; # _Robert Israel_, Jul 14 2024
%o A354182 (PARI) s=0; for (n=0, 67, for (v=0, oo, if (!bittest(s,v) && bitand(n, n+v)==0, print1 (v", "); s+=2^v; break)))
%o A354182 (Python)
%o A354182 from itertools import count, islice
%o A354182 def agen(): # generator of terms
%o A354182     aset, k, mink = set(), 0, 1
%o A354182     for n in count(1):
%o A354182         aset.add(k); yield k; k = mink
%o A354182         while k in aset or n&(n+k): k += 1
%o A354182         while mink in aset: mink += 1
%o A354182 print(list(islice(agen(), 68))) # _Michael S. Branicky_, May 18 2022
%Y A354182 Cf. A001045, A065190.
%K A354182 nonn,base
%O A354182 0,3
%A A354182 _Rémy Sigrist_, May 18 2022