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
Paolo Xausa, Table of n, a(n) for n = 0..10000 (terms 0..1023 from T. D. Noe)
Lukas Spiegelhofer and Michael Wallner, Divisibility of binomial coefficients by powers of primes, arXiv:1604.07089 [math.NT], 2016. Mentions this sequence.
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
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 *)
Table[BitLength[k] - 1 - IntegerExponent[k, 2], {k, 100}] (* Paolo Xausa, Oct 01 2024 *)
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
(PARI) a(n) = exponent(n+1) - valuation(n+1, 2); \\ Antoine Mathys, Nov 20 2024
(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
KEYWORD
easy,nonn,base,changed
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