cp's OEIS Frontend

A057168 Next larger integer with same binary weight (number of 1 bits) as n.

%I A057168 #56 Mar 08 2025 14:25:41
%S A057168 2,4,5,8,6,9,11,16,10,12,13,17,14,19,23,32,18,20,21,24,22,25,27,33,26,
%T A057168 28,29,35,30,39,47,64,34,36,37,40,38,41,43,48,42,44,45,49,46,51,55,65,
%U A057168 50,52,53,56,54,57,59,67,58,60,61,71,62,79,95,128,66,68,69,72,70,73,75
%N A057168 Next larger integer with same binary weight (number of 1 bits) as n.
%C A057168 Binary weight is given by A000120.
%D A057168 Donald Knuth, The Art of Computer Programming, Vol. 4A, section 7.1.3, exercises 20-21.
%H A057168 Reinhard Zumkeller, <a href="/A057168/b057168.txt">Table of n, a(n) for n = 1..10000</a>
%H A057168 M. Beeler, R. W. Gosper, and R. Schroeppel, <a href="https://dspace.mit.edu/handle/1721.1/6086">HAKMEM</a>, MIT Artificial Intelligence Laboratory, Memo AIM-239, February 1972, Item 175 by Gosper, page 81.  Also <a href="http://www.inwap.com/pdp10/hbaker/hakmem/hacks.html#item175">HTML transcription</a>.
%H A057168 Donald E. Knuth, <a href="http://www-cs-faculty.stanford.edu/~knuth/fasc1a.ps.gz">The Art of Computer Programming, Pre-Fascicle 1A</a>, Draft of Section 7.1.3, 2008.  Exercises 20 and 21 page 54 and answers pages 75-76.
%H A057168 Marc B. Reynolds, <a href="https://marc-b-reynolds.github.io/math/2023/11/09/PopNextPrev.html">Popcount walks: next, previous, toward and nearest</a> (2023)
%F A057168 From _Reinhard Zumkeller_, Aug 18 2008: (Start)
%F A057168 a(A000079(n)) = A000079(n+1);
%F A057168 a(A000051(n)) = A052548(n);
%F A057168 a(A052548(n)) = A140504(n);
%F A057168 a(A000225(n)) = A055010(n);
%F A057168 a(A007283(n)) = A000051(n+2). (End)
%F A057168 a(n) = MIN{m: A000120(m)=A000120(n) and m>n}. - _Reinhard Zumkeller_, Aug 15 2009
%F A057168 For k,m>0, a((2^k-1)*2^m) = 2^(k+m)+2^(k-1)-1. - _Chai Wah Wu_, Mar 07 2025
%F A057168 If n is odd, then a(n) = XOR(n,OR(a,a/2)) where a = AND(-n,n+1). - _Chai Wah Wu_, Mar 08 2025
%e A057168 a(6)=9 since 6 has two one-bits (i.e., 6=2+4) and 9 is the next higher integer of binary weight two (7 is weight three and 8 is weight one).
%t A057168 a[n_] := (bw = DigitCount[n, 2, 1]; k = n+1; While[ DigitCount[k, 2, 1] != bw, k++]; k); Table[a[n], {n, 1, 71}](* _Jean-François Alcover_, Nov 28 2011 *)
%o A057168 (PARI) a(n)=my(u=bitand(n,-n),v=u+n);(bitxor(v,n)/u)>>2+v \\ _Charles R Greathouse IV_, Oct 28 2009
%o A057168 (PARI) A057168(n)=n+bitxor(n,n+n=bitand(n,-n))\n\4+n \\ _M. F. Hasler_, Aug 27 2014
%o A057168 (Haskell)
%o A057168 a057168 n = a057168_list !! (n-1)
%o A057168 a057168_list = f 2 $ tail a000120_list where
%o A057168    f x (z:zs) = (x + length (takeWhile (/= z) zs)) : f (x + 1) zs
%o A057168 -- _Reinhard Zumkeller_, Aug 26 2012
%o A057168 (Python)
%o A057168 def a(n): u = n&-n; v = u+n; return (((v^n)//u)>>2)+v
%o A057168 print([a(n) for n in range(1, 72)]) # _Michael S. Branicky_, Jul 10 2022 after _Charles R Greathouse IV_
%o A057168 (Python)
%o A057168 def A057168(n): return ((n&~(b:=n+(a:=n&-n)))>>a.bit_length())^b # _Chai Wah Wu_, Mar 06 2025
%Y A057168 Cf. A000120, A006519, A057169, A000051, A052548, A140504, A000225, A055010, A007283, A171942.
%Y A057168 Cf. A000079, A018900, A014311, A014312, A014313, A023688, A023689, A023690, A023691 (Hamming weight = 1, 2, ..., 9).
%K A057168 easy,nonn,nice
%O A057168 1,1
%A A057168 _Marc LeBrun_, Sep 14 2000