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.

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, 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, 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

Offset

0,5

Comments

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

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

Links

T. D. Noe, Table of n, a(n) for n = 0..1023

Lukas Spiegelhofer and Michael Wallner, Divisibility of binomial coefficients by powers of primes, arXiv:1604.07089 [math.NT], 2016. Mentions this sequence.

Index entries for sequences related to binary expansion of n

Formula

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

a(A000225(n))=0. - R. J. Mathar, Jul 29 2006

a(n) = -valuation(H(n)*n,2) where H(n) is the n-th harmonic number. - Benoit Cloitre, Oct 13 2013

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]

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

a(n) = floor(log_2(A000265(n+1))). - Laura Monroe, Oct 18 2020

a(n) = A070939(n+1) - A001511(n+1). - David James Sycamore, Feb 24 2023

Example

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.
From David James Sycamore, Feb 26 2023: (Start)
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:
n = 2^k - 1: distance between 1's in n+1 = 2^k is 0; a(n) = 0 (all bits change).
82 in binary is 1010010, and 83 is 1010011 distance between 1's in 83 = 6 = a(82).
Show visually for a(327) = 5:
 n   = 327 = 101000111
             ^^^^^      5 unchanged bits.
 n+1 = 328 = 101001000
             ^    ^     distance between 1's = 5. (End)

Maple

a:= n-> ilog2(n+1)-padic[ordp](n+1, 2):
seq(a(n), n=0..128);  # Alois P. Heinz, Jun 28 2021

Mathematica

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 *)
(* Second program, faster *)
Array[Last[#] - First[#] &@ Position[IntegerDigits[#, 2], 1][[All, 1]] &, 2^14] (* Michael De Vlieger, Feb 22 2023 *)

Prog

(C)
#include <stdio.h>
#define NMAX 200
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 ; }
int main(int argc, char*argv[])
{ for(int n=0; n<NMAX; n++) printf("%d, ", sameD(n, n+1)) ; return 0 ; }
/* R. J. Mathar, Jul 29 2006 */
(Haskell)
a119387 n = length $ takeWhile (< a070940 n) [1..n]
-- Reinhard Zumkeller, Apr 22 2013
(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 */
(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
(C)
int A119387(int n)
{
    int m=n+1;
    while (!(m&1)) m>>=1;
    int m_bits = 0;
    while (m>>=1) m_bits++;
    return m_bits;
}
/* Laura Monroe, Oct 18 2020 */
(Python)
def A119387(n): return (n+1).bit_length()-(n+1&-n-1).bit_length() # Chai Wah Wu, Jul 07 2022

Crossrefs

Cf. A048881, A086784.

Cf. A070940.

Cf. A000265.

Cf. A001511, A070939.

Cf. A373709 (partial sums).

Sequence in context: A147786 A275019 A337835 * A335905 A055941 A347696

Adjacent sequences: A119384 A119385 A119386 * A119388 A119389 A119390

Keyword

easy,nonn,base

Author

Leroy Quet, Jul 26 2006

Extensions

More terms from R. J. Mathar, Jul 29 2006

Edited by Charles R Greathouse IV, Aug 04 2010

Status

approved