A303763 Permutation of nonnegative integers: a(0) = 0 and for n > 0, a(n) = the least k for which bitor(k,a(n-1)) = a(n-1) and k is not already present, and otherwise, if no such k exists, the least number not already present that can be obtained by cumulatively filling the successive vacant bits of a(n-1) from its least significant end (by toggling 0's to 1's, possibly also one or more leading zeros).
0, 1, 3, 2, 7, 4, 5, 15, 6, 31, 8, 9, 11, 10, 63, 12, 13, 127, 14, 255, 16, 17, 19, 18, 23, 20, 21, 511, 22, 1023, 24, 25, 27, 26, 2047, 28, 29, 4095, 30, 8191, 32, 33, 35, 34, 39, 36, 37, 47, 38, 16383, 40, 41, 43, 42, 32767, 44, 45, 65535, 46, 131071, 48, 49, 51, 50, 55, 52, 53, 262143, 54, 524287, 56, 57, 59, 58, 1048575, 60, 61
Offset: 0
Examples
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 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 "100" = 4 is the least one of these not already present, 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 zeros from the right, we first obtain "...0111" = 7, which also has been used, so we continue filling the zeros, to obtain next "...1111" = 15, which is still free, so a(7) = 15. For a(8), previous = 15, "..1111" in binary, and its least unused submask is "110" = 6, thus a(8) = 6.
Links
Programs
-
PARI
up_to = (2^14)-1; A006519(n) = (2^valuation(n, 2)); v303763 = vector(up_to); m303764 = Map(); prev=1; for(n=1,up_to,for(m=1,prev,if((bitor(prev,m)==prev) && !mapisdefined(m303764,m),v303763[n] = m;mapput(m303764,m,n);break)); if(!v303763[n], while(mapisdefined(m303764,prev), prev += A006519(1+prev)); v303763[n] = prev; mapput(m303764,prev,n)); prev = v303763[n]); A303763(n) = if(!n,n,v303763[n]); A303764(n) = if(!n,n,mapget(m303764,n));
Comments