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

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, 27, 31, 23, 21, 29, 28, 60, 44, 40, 32, 33, 35, 34, 38, 36, 37, 39, 47, 41, 43, 42, 46, 62, 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

Offset: 0

Author

Antti Karttunen, May 05 2018

Keywords

• nonn
• base

Comments

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.

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.

Links

• Antti Karttunen, Table of n, a(n) for n = 0..13232
• Index entries for sequences related to binary expansion of n
• Index entries for sequences that are permutations of the natural numbers
• Index entries for sequences computed from indices in prime factorization

Crossrefs

Cf. A303774 (inverse).

Cf. A303770.

Cf. A303763, A303765, A303767, A303775 for similar constructions.

Programs

PARI

up_to = (2^18)-1;
A006519(n) = (2^valuation(n, 2));
A003961(n) = my(f = factor(n)); for (i=1, #f~, f[i, 1] = nextprime(f[i, 1]+1)); factorback(f); \\ From A003961
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)};
v303773 = vector(up_to);
m303774 = Map();
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));
A303773(n) = if(!n,n,v303773[n]);
A303774(n) = if(!n,n,mapget(m303774,n));

Formula

For all n >= 0, A019565(a(n)) = A303770(n).