cp's OEIS Frontend

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.

%I A243109 #39 Apr 10 2025 23:21:30
%S A243109 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,
%T A243109 23,26,27,29,31,16,24,33,28,34,35,37,30,36,38,41,39,42,43,45,31,40,44,
%U A243109 49,46,50,51,53,47,52,54,57,55,58,59,61,63,32,48,65,56,66,67,69
%N 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.
%C A243109 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
%H A243109 Philippe Beaudoin, <a href="/A243109/b243109.txt">Table of n, a(n) for n = 0..10000</a>
%H A243109 Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, 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).
%F A243109 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
%F A243109 For k,m > 0, a((2^k-1)*2^m) = 2^(m-1)*(2^(k+1)-3). - _Chai Wah Wu_, Mar 07 2025
%F A243109 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
%e A243109 From _Kevin Ryde_, Mar 01 2021: (Start)
%e A243109                            v    vv
%e A243109      n = 1475 = binary 10111000011    lowest 10 of n
%e A243109   a(n) = 1464 = binary 10110111000    becomes 01 and
%e A243109                             ^^^       other 1's below
%e A243109 (End)
%t A243109 A243109[n_] := If[# == 0, n, # - 2^(IntegerExponent[#, 2] - IntegerExponent[n+1, 2] - 1)] & [BitAnd[n, n+1]];
%t A243109 Array[A243109, 100, 0] (* _Paolo Xausa_, Mar 07 2025 *)
%o A243109 (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
%o A243109 (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
%o A243109 (Python)
%o A243109 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
%Y A243109 Cf. A057168 (next of same weight), A066884 (array by weight), A241816 (lowest 10->01).
%K A243109 nonn,base,easy
%O A243109 0,4
%A A243109 _Philippe Beaudoin_, Aug 20 2014