cp's OEIS Frontend

A303773 Permutation of nonnegative integers constructed with a greedy algorithm producing either-subset-or-superset-mask type of walk in binary lattice (see comments for the exact definition).

%I A303773 #11 May 06 2018 00:49:46
%S A303773 0,1,3,2,6,4,5,7,15,11,10,8,9,13,12,14,30,22,20,16,17,19,18,26,24,25,
%T A303773 27,31,23,21,29,28,60,44,40,32,33,35,34,38,36,37,39,47,41,43,42,46,62,
%U A303773 58,50,48,49,51,55,53,52,54,118,82,66,64,65,67,71,69,68,70,78,74,72,73,75,79,77,76,92,88,80,81,83,87,85,84,86,94,90,91,89,93,95,127
%N A303773 Permutation of nonnegative integers constructed with a greedy algorithm producing either-subset-or-superset-mask type of walk in binary lattice (see comments for the exact definition).
%C A303773 a(0) = 0 and for n > 0, if there are one or more k_i that are not already present in the sequence among terms a(0) .. a(n-1), and for which bitor(k_i,a(n-1)) = a(n-1), then a(n) = that k_i which gives minimum value of A003961(k_i) amongst them; otherwise, when no such k_i exists, a(n) = the least number not already present that can be obtained by toggling a single 0-bit of a(n-1) to 1. This is done by trying to toggle successive vacant bits from the least significant end of the binary representation of a(n-1), until such a sum a(n-1) + 2^h (= a(n-1) bitxor 2^h) is found that is not already present in the sequence.
%C A303773 Shares with permutations like A003188, A006068, A163252, A300838, A302846, A303763, A303765, A303767 and A303775 the property that when moving from any a(n) to a(n+1) either a subset of 0-bits are toggled on (changed to 1's, in this case always only a single bit), or a subset of 1-bits are toggled off (changed to 0's), but no both kind of changes may occur at the same step.
%H A303773 Antti Karttunen, <a href="/A303773/b303773.txt">Table of n, a(n) for n = 0..13232</a>
%H A303773 <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>
%H A303773 <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%H A303773 <a href="/index/Pri#prime_indices">Index entries for sequences computed from indices in prime factorization</a>
%F A303773 For all n >= 0, A019565(a(n)) = A303770(n).
%o A303773 (PARI)
%o A303773 up_to = (2^18)-1;
%o A303773 A006519(n) = (2^valuation(n, 2));
%o A303773 A003961(n) = my(f = factor(n)); for (i=1, #f~, f[i, 1] = nextprime(f[i, 1]+1)); factorback(f); \\ From A003961
%o A303773 A064989(n) = {my(f); f = factor(n); if((n>1 && f[1,1]==2), f[1,2] = 0); for (i=1, #f~, f[i,1] = precprime(f[i,1]-1)); factorback(f)};
%o A303773 v303773 = vector(up_to);
%o A303773 m303774 = Map();
%o A303773 w=1; for(n=1,up_to,s = Set([]); for(m=1,w, if((bitor(w,m)==w) && !mapisdefined(m303774,m), s = setunion(Set([A003961(m)]),s))); if(length(s)>0, w = A064989(vecmin(s)), b=A006519(1+w); while(bitand(w,b) || mapisdefined(m303774,w+b), b <<= 1); w += b); v303773[n] = w; mapput(m303774,w,n));
%o A303773 A303773(n) = if(!n,n,v303773[n]);
%o A303773 A303774(n) = if(!n,n,mapget(m303774,n));
%Y A303773 Cf. A303774 (inverse).
%Y A303773 Cf. A303770.
%Y A303773 Cf. A303763, A303765, A303767, A303775 for similar constructions.
%K A303773 nonn,base
%O A303773 0,3
%A A303773 _Antti Karttunen_, May 05 2018