A119387 - OEIS

%I #128 Oct 01 2024 08:50:53

%S 0,0,1,0,2,1,2,0,3,2,3,1,3,2,3,0,4,3,4,2,4,3,4,1,4,3,4,2,4,3,4,0,5,4,

%T 5,3,5,4,5,2,5,4,5,3,5,4,5,1,5,4,5,3,5,4,5,2,5,4,5,3,5,4,5,0,6,5,6,4,

%U 6,5,6,3,6,5,6,4,6,5,6,2,6,5,6,4,6,5,6,3,6,5,6,4,6,5,6,1,6,5,6,4,6,5,6,3,6

%N a(n) is the number of binary digits (1's and nonleading 0's) which remain unchanged in their positions when n and (n+1) are written in binary.

%C The largest k for which A220645(n,k) > 0 is k = a(n). That is, a(n) is the largest power of 2 that divides binomial(n,i) for 0 <= i <= n. - _T. D. Noe_, Dec 18 2012

%C a(n) is the distance between the first and last 1's in the binary expansion of n+1; see examples and formulae. - _David James Sycamore_, Feb 21 2023

%H Paolo Xausa, <a href="/A119387/b119387.txt">Table of n, a(n) for n = 0..10000</a> (terms 0..1023 from T. D. Noe)

%H Lukas Spiegelhofer and Michael Wallner, <a href="https://arxiv.org/abs/1604.07089">Divisibility of binomial coefficients by powers of primes</a>, arXiv:1604.07089 [math.NT], 2016. Mentions this sequence.

%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>

%F a(n) = A048881(n) + A086784(n+1). (A048881(n) is the number of 1's which remain unchanged between binary n and (n+1). A086784(n+1) is the number of nonleading 0's which remain unchanged between binary n and (n+1).)

%F a(A000225(n))=0. - _R. J. Mathar_, Jul 29 2006

%F a(n) = -valuation(H(n)*n,2) where H(n) is the n-th harmonic number. - _Benoit Cloitre_, Oct 13 2013

%F a(n) = A000523(n+1) - A007814(n+1) = floor(log(n+1)/log(2)) - valuation(n+1,2). - _Benoit Cloitre_, Oct 13 2013 [corrected by _David James Sycamore_, Feb 28 2023]

%F Recurrence: a(2n) = floor(log_2(n)) except a(0) = 0, a(2n+1) = a(n). - _Ralf Stephan_, Oct 16 2013, corrected by _Peter J. Taylor_, Mar 01 2020

%F a(n) = floor(log_2(A000265(n+1))). - _Laura Monroe_, Oct 18 2020

%F a(n) = A070939(n+1) - A001511(n+1). - _David James Sycamore_, Feb 24 2023

%e 9 in binary is 1001. 10 (decimal) is 1010 in binary. 2 binary digits remain unchanged (the leftmost two digits) between 1001 and 1010. So a(9) = 2.

%e From _David James Sycamore_, Feb 26 2023: (Start)

%e Number of bits surviving transition from n to n+1 = distance between first and last 1's in binary expansion of n+1 (no need to compare n and n+1). Examples:

%e n = 2^k - 1: distance between 1's in n+1 = 2^k is 0; a(n) = 0 (all bits change).

%e 82 in binary is 1010010, and 83 is 1010011 distance between 1's in 83 = 6 = a(82).

%e Show visually for a(327) = 5:

%e  n   = 327 = 101000111

%e              ^^^^^      5 unchanged bits.

%e  n+1 = 328 = 101001000

%e              ^    ^     distance between 1's = 5. (End)

%p a:= n-> ilog2(n+1)-padic[ordp](n+1, 2):

%p seq(a(n), n=0..128);  # _Alois P. Heinz_, Jun 28 2021

%t a = {0}; Table[b = IntegerDigits[n, 2]; If[Length[a] == Length[b], c = 1; While[a[[c]] == b[[c]], c++]; c--, c = 0]; a = b; c, {n, 101}] (* _T. D. Noe_, Dec 18 2012 *)

%t (* Second program, faster *)

%t Array[Last[#] - First[#] &@ Position[IntegerDigits[#, 2], 1][[All, 1]] &, 2^14] (* _Michael De Vlieger_, Feb 22 2023 *)

%t Table[BitLength[k] - 1 - IntegerExponent[k, 2], {k, 100}] (* _Paolo Xausa_, Oct 01 2024 *)

%o (C)

%o #include <stdio.h>

%o #define NMAX 200

%o int sameD(int a, int b) { int resul=0 ; while(a>0 && b >0) { if( (a &1) == (b & 1)) resul++ ; a >>= 1 ; b >>= 1 ; } return resul ; }

%o int main(int argc, char*argv[])

%o { for(int n=0;n<NMAX;n++) printf("%d,",sameD(n,n+1)) ; return 0 ; }

%o /* _R. J. Mathar_, Jul 29 2006 */

%o (Haskell)

%o a119387 n = length $ takeWhile (< a070940 n) [1..n]

%o -- _Reinhard Zumkeller_, Apr 22 2013

%o (PARI) a(n) = n++; local(c); c=0; while(2^(c+1)<n+1, c=c+1); c-valuation(n, 2); /* _Ralf Stephan_, Oct 16 2013; corrected by _Michel Marcus_, Jun 28 2021 */

%o (PARI) a(n) = my(x=Vecrev(binary(n)), y=Vecrev(binary(n+1))); sum(k=1, min(#x, #y), x[k] == y[k]); \\ _Michel Marcus_, Jun 27 2021

%o (C)

%o int A119387(int n)

%o {

%o     int m=n+1;

%o     while (!(m&1)) m>>=1;

%o     int m_bits = 0;

%o     while (m>>=1) m_bits++;

%o     return m_bits;

%o }

%o /* _Laura Monroe_, Oct 18 2020 */

%o (Python)

%o def A119387(n): return (n+1).bit_length()-(n+1&-n-1).bit_length() # _Chai Wah Wu_, Jul 07 2022

%Y Cf. A048881, A086784.

%Y Cf. A070940.

%Y Cf. A000265.

%Y Cf. A001511, A070939.

%Y Cf. A373709 (partial sums).

%K easy,nonn,base

%O 0,5

%A _Leroy Quet_, Jul 26 2006

%E More terms from _R. J. Mathar_, Jul 29 2006

%E Edited by _Charles R Greathouse IV_, Aug 04 2010