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

%I #44 Nov 17 2023 22:52:32

%S 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 28,29,35,30,39,47,64,34,36,37,40,38,41,43,48,42,44,45,49,46,51,55,65,

%U 50,52,53,56,54,57,59,67,58,60,61,71,62,79,95,128,66,68,69,72,70,73,75

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

%C Binary weight is given by A000120.

%D Donald Knuth, The Art of Computer Programming, Vol. 4A, section 7.1.3, exercises 20-21.

%H Reinhard Zumkeller, <a href="/A057168/b057168.txt">Table of n, a(n) for n = 1..10000</a>

%H 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 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 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 From _Reinhard Zumkeller_, Aug 18 2008: (Start)

%F a(A000079(n)) = A000079(n+1);

%F a(A000051(n)) = A052548(n);

%F a(A052548(n)) = A140504(n);

%F a(A000225(n)) = A055010(n);

%F a(A007283(n)) = A000051(n+2). (End)

%F a(n) = MIN{m: A000120(m)=A000120(n) and m>n}. - _Reinhard Zumkeller_, Aug 15 2009

%e 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 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 (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 (PARI) A057168(n)=n+bitxor(n,n+n=bitand(n,-n))\n\4+n \\ _M. F. Hasler_, Aug 27 2014

%o (Haskell)

%o a057168 n = a057168_list !! (n-1)

%o a057168_list = f 2 $ tail a000120_list where

%o f x (z:zs) = (x + length (takeWhile (/= z) zs)) : f (x + 1) zs

%o -- _Reinhard Zumkeller_, Aug 26 2012

%o (Python)

%o def a(n): u = n&-n; v = u+n; return (((v^n)//u)>>2)+v

%o print([a(n) for n in range(1, 72)]) # _Michael S. Branicky_, Jul 10 2022 after _Charles R Greathouse IV_

%Y Cf. A000120, A006519, A057169, A000051, A052548, A140504, A000225, A055010, A007283, A171942.

%Y Cf. A000079, A018900, A014311, A014312, A014313, A023688, A023689, A023690, A023691 (Hamming weight = 1, 2, ..., 9).

%K easy,nonn,nice

%O 1,1

%A _Marc LeBrun_, Sep 14 2000