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.

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

Author

Philippe Beaudoin, Aug 20 2014

Keywords

• nonn
• base
• easy

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

Examples

			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)
		

Links

• Philippe Beaudoin, Table of n, a(n) for n = 0..10000
• 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).

Crossrefs

Cf. A057168 (next of same weight), A066884 (array by weight), A241816 (lowest 10->01).

Programs

Mathematica

A243109[n_] := If[# == 0, n, # - 2^(IntegerExponent[#, 2] - IntegerExponent[n+1, 2] - 1)] & [BitAnd[n, n+1]];
Array[A243109, 100, 0] (* Paolo Xausa, Mar 07 2025 *)

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

Python

def A243109(n): return c if (c:=((~n&(b:=n-(a:=~n&n+1)))>>a.bit_length())^b) else n # Chai Wah Wu, Mar 06 2025

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

For k,m > 0, a((2^k-1)*2^m) = 2^(m-1)*(2^(k+1)-3). - Chai Wah Wu, Mar 07 2025

If n is even, then a(n) = XOR(n,OR(a,a/2)) where a = AND(-n,n+1). - Chai Wah Wu, Mar 08 2025