cp's OEIS Frontend

A119387 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.

%I A119387 #138 Nov 22 2024 16:51:07
%S A119387 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 A119387 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 A119387 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 A119387 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 A119387 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 A119387 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 A119387 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 A119387 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 A119387 <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>
%F A119387 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 A119387 a(A000225(n))=0. - _R. J. Mathar_, Jul 29 2006
%F A119387 a(n) = -valuation(H(n)*n,2) where H(n) is the n-th harmonic number. - _Benoit Cloitre_, Oct 13 2013
%F A119387 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 A119387 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 A119387 a(n) = floor(log_2(A000265(n+1))). - _Laura Monroe_, Oct 18 2020
%F A119387 a(n) = A070939(n+1) - A001511(n+1). - _David James Sycamore_, Feb 24 2023
%e A119387 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 A119387 From _David James Sycamore_, Feb 26 2023: (Start)
%e A119387 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 A119387 n = 2^k - 1: distance between 1's in n+1 = 2^k is 0; a(n) = 0 (all bits change).
%e A119387 82 in binary is 1010010, and 83 is 1010011 distance between 1's in 83 = 6 = a(82).
%e A119387 Show visually for a(327) = 5:
%e A119387  n   = 327 = 101000111
%e A119387              ^^^^^      5 unchanged bits.
%e A119387  n+1 = 328 = 101001000
%e A119387              ^    ^     distance between 1's = 5. (End)
%p A119387 a:= n-> ilog2(n+1)-padic[ordp](n+1, 2):
%p A119387 seq(a(n), n=0..128);  # _Alois P. Heinz_, Jun 28 2021
%t A119387 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 A119387 (* Second program, faster *)
%t A119387 Array[Last[#] - First[#] &@ Position[IntegerDigits[#, 2], 1][[All, 1]] &, 2^14] (* _Michael De Vlieger_, Feb 22 2023 *)
%t A119387 Table[BitLength[k] - 1 - IntegerExponent[k, 2], {k, 100}] (* _Paolo Xausa_, Oct 01 2024 *)
%o A119387 (C)
%o A119387 #include <stdio.h>
%o A119387 #define NMAX 200
%o A119387 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 A119387 int main(int argc, char*argv[])
%o A119387 { for(int n=0;n<NMAX;n++) printf("%d,",sameD(n,n+1)) ; return 0 ; }
%o A119387 /* _R. J. Mathar_, Jul 29 2006 */
%o A119387 (Haskell)
%o A119387 a119387 n = length $ takeWhile (< a070940 n) [1..n]
%o A119387 -- _Reinhard Zumkeller_, Apr 22 2013
%o A119387 (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 A119387 (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 A119387 (PARI) a(n) = exponent(n+1) - valuation(n+1, 2); \\ _Antoine Mathys_, Nov 20 2024
%o A119387 (C)
%o A119387 int A119387(int n)
%o A119387 {
%o A119387     int m=n+1;
%o A119387     while (!(m&1)) m>>=1;
%o A119387     int m_bits = 0;
%o A119387     while (m>>=1) m_bits++;
%o A119387     return m_bits;
%o A119387 }
%o A119387 /* _Laura Monroe_, Oct 18 2020 */
%o A119387 (Python)
%o A119387 def A119387(n): return (n+1).bit_length()-(n+1&-n-1).bit_length() # _Chai Wah Wu_, Jul 07 2022
%Y A119387 Cf. A048881, A086784.
%Y A119387 Cf. A070940.
%Y A119387 Cf. A000265.
%Y A119387 Cf. A001511, A070939.
%Y A119387 Cf. A373709 (partial sums).
%K A119387 easy,nonn,base
%O A119387 0,5
%A A119387 _Leroy Quet_, Jul 26 2006
%E A119387 More terms from _R. J. Mathar_, Jul 29 2006
%E A119387 Edited by _Charles R Greathouse IV_, Aug 04 2010