login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 4
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 (list; graph; refs; listen; history; text; internal format)
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

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) - A007814(n) = floor(log(n)/log(2)) - valuation(n,2). - Benoit Cloitre, Oct 13 2013

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

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.

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

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 */

CROSSREFS

Cf. A048881, A086784.

Cf. A070940.

Cf. A000265.

Sequence in context: A147786 A275019 A337835 * A335905 A055941 A290537

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 17 06:16 EDT 2021. Contains 347478 sequences. (Running on oeis4.)