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