login
A303765
Permutation of nonnegative integers: a(n) = A048675(A303761(n)); see comments for an equivalent alternative description.
11
0, 1, 3, 2, 7, 4, 5, 15, 8, 9, 11, 10, 31, 16, 17, 19, 18, 23, 6, 63, 32, 33, 35, 34, 39, 36, 37, 47, 12, 13, 127, 64, 65, 67, 66, 71, 68, 69, 79, 14, 255, 128, 129, 131, 130, 135, 132, 133, 143, 136, 137, 139, 138, 159, 20, 21, 511, 256, 257, 259, 258, 263, 260, 261, 271, 264, 265, 267, 266, 287, 24, 25, 27, 26, 1023, 512, 513, 515, 514, 519, 516, 517, 527
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 A019565(k_i) amongst them; otherwise, when no such k_i exists, a(n) = the least number not already present that can be obtained by cumulatively filling the successive vacant bits of a(n-1) from the least significant end of its binary representation (by toggling 0's to 1's, possibly also one or more leading zeros).
Shares with permutations like A003188, A006068, A300838, A302846, A303763, and A303767 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), 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.
A300829 gives the positions of records (terms of A000225 in ascending order), that for cases n=2..79 are followed by 2^(n-1).
FORMULA
a(n) = A048675(A303761(n)).
For all n >= 0, A019565(a(n)) = A303761(n).
EXAMPLE
For a(2), a(1) = 1, and the only subset mask (a number k for which bitor(k,1) = k) is 1 itself, already present, so we start toggling 0's to 1's with binary expansion "...00001" of 1, and we get "11" (= binary representation of 3), and 3 is not yet present, thus a(2) = 3.
For a(3), previous a(2) = 3, "...011" in binary, and "10" (= 2) is the least and only submask that is not already present, thus a(3) = 2.
For a(4), previous = 2, "...010" in binary, and there are no submasks that are not already used, thus we start toggling 0's to 1's from the right, and "11" (3) is already present, but "111" (7) is not, thus a(4) = 7.
For a(5), previous = 7, with seven submasks "1", "10", "11", "100", "101", "110", "111" (binary representations for 1 - 7), and of these "100", "101", "110" (4, 5 and 6) are not yet present. A019565(4) = 5, A019565(5) = 10 and A019565(6) = 15, so we choose the first one, thus a(5) = 4.
For a(6), previous = 4, "..0100" in binary, and no submasks that wouldn't have been already used, thus by toggling from the right, we first obtain "...0101" = 5, which is still free, so a(6) = 5.
For a(7), previous = 5, "..0101" in binary, and no submasks that would be free (both 1 and 4 are already present), thus by toggling from the right, we first obtain "...0111" = 7, which also has been used, so we continue filling the zeros, to next obtain "...1111" = 15, which is still free, so a(7) = 15.
For a(8), previous = 15, "..1111" in binary, and the submasks not used are "110" = 6, "1000" = 8, "1001" = 9, "1010" = 10, "1011" = 11, "1100" = 12, "1101" = 13 and "1110" = 14. Applying A019565 to these numbers, A019565(8) = 7 gives the smallest value, thus a(8) = 8.
PROG
(PARI)
up_to = (2^7)-1;
A006519(n) = (2^valuation(n, 2));
A019565(n) = {my(j, v); factorback(Mat(vector(if(n, #n=vecextract(binary(n), "-1..1")), j, [prime(j), n[j]])~))}; \\ From A019565
A048675(n) = { my(f = factor(n)); sum(k=1, #f~, f[k, 2]*2^primepi(f[k, 1]))/2; };
v303765 = vector(up_to);
m303766 = Map();
w=1; for(n=1, up_to, s = Set([]); for(m=1, w, if((bitor(w, m)==w) && !mapisdefined(m303766, m), s = setunion(Set([A019565(m)]), s))); if(length(s)>0, w = A048675(vecmin(s)), while(mapisdefined(m303766, w), w += A006519(1+w))); v303765[n] = w; mapput(m303766, w, n));
A303765(n) = if(!n, n, v303765[n]);
A303766(n) = if(!n, n, mapget(m303766, n));
CROSSREFS
Cf. A303766 (inverse).
Cf. A303763, A303767 (variants).
Cf. A300829 (positions of records).
Sequence in context: A375890 A370698 A303763 * A255555 A191664 A118319
KEYWORD
nonn,base
AUTHOR
Antti Karttunen, May 02 2018
STATUS
approved