|
|
A070940
|
|
Number of digits that must be counted from left to right to reach the last 1 in the binary representation of n.
|
|
11
|
|
|
1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 4, 2, 4, 3, 4, 1, 5, 4, 5, 3, 5, 4, 5, 2, 5, 4, 5, 3, 5, 4, 5, 1, 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, 7, 6, 7, 5, 7, 6, 7, 4, 7, 6, 7, 5, 7, 6, 7, 3, 7, 6, 7, 5, 7, 6, 7, 4, 7, 6, 7, 5, 7
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
Length of longest carry sequence when adding numbers <= n to n in binary representation: a(n) = T(n, A080079(n)) and T(n,k) <= a(n) for 1 <= k <= n, with T defined as in A080080. - Reinhard Zumkeller, Jan 26 2003
a(n+1) is the number of distinct values of gcd(2^n, binomial(n,j)) (or, equivalently, A007814(binomial(n,j))) arising for j=0..n-1. Proof using Kummer's Theorem given by Marc Schwartz. - Labos Elemer, Apr 23 2003
E.g., n=10: 10th row of Pascal's triangle = {1,10,45,120,210,252,210,120,45,10,1}, largest powers of 2 dividing binomial coefficients is: {1,2,1,8,2,4,2,8,1,2,1}; including distinct powers of 2, thus a(10)=4. If m=-1+2^k, i.e., m=0,1,3,7,15,31,... then a(m)=1. This corresponds to "odd rows" of Pascal's triangle. - Labos Elemer
Can be regarded as a table with row n having 2^(n-1) columns, with odd columns repeating the previous row, and even columns containing the row number. - Franklin T. Adams-Watters, Nov 08 2011
It appears that a(n) is the greatest number in a periodicity equivalence class defined at A269570; e.g., the 5 classes for n = 35 are (1, 1, 2, 2, 6), (1, 1, 1, 1, 4, 2, 2), (3), (1, 3), (1, 2); in these the greatest number is 6, so that a(35) = 6. - Clark Kimberling, Mar 01 2016
Number of binary digits of the largest odd factor of n. - Andres Cicuttin, May 18 2017
|
|
LINKS
|
|
|
FORMULA
|
a(n) = f(n, 1), f(n, k) = if n=1 then k else f(floor(n/2), k+(if k>1 then 1 else n mod 2)). - Reinhard Zumkeller, Feb 01 2003
G.f.: Sum_{k>=0} (t/(1-t^2)) * (1 + Sum_{L>=1} t^2^L), where t=x^2^k. - Ralf Stephan, Mar 15 2004
a(1) = 1 and for m >= 0, 0 <= k < 2^m, a(2^(m+1)+2*k) = a(2^m+k), a(2^(m+1)+2*k+1) = m+2. - Yosu Yurramendi, Aug 08 2019
|
|
EXAMPLE
|
a(10)=3 is the number of digits that must be counted from left to right to reach the last 1 in 1010, the binary representation of 10.
The table starts:
1
1 2
1 3 2 3
1 4 3 4 2 4 3 4
|
|
MAPLE
|
|
|
MATHEMATICA
|
Table[Length[Union[Table[GCD[2^n, Binomial[n, j]], {j, 0, n}]]], {n, 0, 256}]
f[n_] := Position[ IntegerDigits[n, 2], 1][[ -1, 1]]; Table[ f[n], {n, 105}] (* Robert G. Wilson v, Dec 01 2004 *)
(* By exploiting the "positional" regularity of the sequence *)
b = {}; a = {1, 1};
Do[a = Riffle[a, j];
b = AppendTo[b, a[[1 ;; Floor[Length[a]/2]]]] // Flatten, {j, 1, 10}];
(* By following the alternative definition "Number of binary digits of the largest integer odd factor of n" *)
c = Table[IntegerDigits[n/(2^IntegerExponent[n, 2]), 2] // Length , {n,
2^10 - 1}];
lidn[n_]:=Module[{idn=IntegerDigits[n, 2]}, idn=If[Last[idn]==0, Flatten[ Most[ Split[ idn]]], idn]; Length[idn]]; Array[lidn, 100] (* Harvey P. Dale, Oct 18 2020 *)
|
|
PROG
|
(Haskell)
(R)
blocklevel <- 7 # by choice
a <- 1
for(m in 0:blocklevel)
for(k in 0:(2^m-1)){
a[2^(m+1)+2*k ] <- a[2^m+k]
a[2^(m+1)+2*k+1] <- m + 2
}
a
(Python)
while n%2 == 0:
n = n//2
a = 0
while n != 0:
n, a = n//2, a+1
return a
n = 0
while n < 100:
n = n+1
(Python)
|
|
CROSSREFS
|
Bisections give A070941 and this sequence (again).
|
|
KEYWORD
|
nonn,nice,easy,tabf
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|