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,3

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

Formula

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

Prog

(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));

Crossrefs

Cf. A303774 (inverse).

Cf. A303770.

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

Sequence in context: A303767 A163252 A340250 * A303769 A303775 A084494

Adjacent sequences: A303770 A303771 A303772 * A303774 A303775 A303776

Keyword

nonn,base

Author

Antti Karttunen, May 05 2018

Status

approved