login
A243109
a(n) is the largest number smaller than n and having the same Hamming weight as n, or n if no such number exist.
2
0, 1, 1, 3, 2, 3, 5, 7, 4, 6, 9, 7, 10, 11, 13, 15, 8, 12, 17, 14, 18, 19, 21, 15, 20, 22, 25, 23, 26, 27, 29, 31, 16, 24, 33, 28, 34, 35, 37, 30, 36, 38, 41, 39, 42, 43, 45, 31, 40, 44, 49, 46, 50, 51, 53, 47, 52, 54, 57, 55, 58, 59, 61, 63, 32, 48, 65, 56, 66, 67, 69
OFFSET
0,4
COMMENTS
To calculate a(n), some bits of n are rearranged. The lowest 1-bit which can move down is the 1 of the lowest 10 bit pair in n. This pair becomes 01 in a(n) and any 1's below there move up to immediately below so the decrease is as small as possible. If n has no 10 bit pair (n = 2^k-1) then nothing smaller is possible and a(n) = n. - Kevin Ryde, Mar 01 2021
LINKS
Joerg Arndt, Matters Computational (The Fxtbook), section 1.24.1 Co-lexicographic (colex) order, function prev_colex_comb(), and second implementation in FXT library bitcombcolex.h (both 0 when no previous rather than a(n) = n).
FORMULA
a(n) = t - 2^(A007814(t) - A007814(n+1) - 1) if t!=0, or a(n) = n if t=0, where t = A129760(n+1) is n with any trailing 1's cleared to 0's and A007814 is the 2-adic valuation. - Kevin Ryde, Mar 01 2021
EXAMPLE
From Kevin Ryde, Mar 01 2021: (Start)
v vv
n = 1475 = binary 10111000011 lowest 10 of n
a(n) = 1464 = binary 10110111000 becomes 01 and
^^^ other 1's below
(End)
PROG
(PARI) a(n) = {my(hn = hammingweight(n)); forstep(k=n-1, 1, -1, if (hammingweight(k) == hn, return (k)); ); return (n); } \\ Michel Marcus, Aug 20 2014
(PARI) a(n) = my(s=n+1, t=bitand(n, s)); if(t==0, n, t - 1<<(valuation(t, 2)-valuation(s, 2)-1)); \\ Kevin Ryde, Mar 01 2021
CROSSREFS
Cf. A057168 (next of same weight), A066884 (array by weight), A241816 (lowest 10->01).
Sequence in context: A351705 A246592 A241816 * A206012 A211940 A230664
KEYWORD
nonn,base,easy
AUTHOR
Philippe Beaudoin, Aug 20 2014
STATUS
approved