%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