login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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). 7
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

Shares with permutations like A003188, A006068, A300838, A302846, A303765, 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.

LINKS

Antti Karttunen, Table of n, a(n) for n = 0..2047

Index entries for sequences related to binary expansion of n

Index entries for sequences that are permutations of the natural numbers

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

PROG

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

CROSSREFS

Cf. A303764 (inverse).

Cf. A303765, A303767 for similar permutations.

Sequence in context: A277679 A108644 A194011 * A303765 A255555 A191664

Adjacent sequences:  A303760 A303761 A303762 * A303764 A303765 A303766

KEYWORD

nonn,base

AUTHOR

Antti Karttunen, May 02 2018

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 8 18:44 EDT 2020. Contains 335524 sequences. (Running on oeis4.)