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
Smallest x > 0 for which a(x)=n equals 2^n. - Labos Elemer
a(n) <= A070939(n), a(n) = A070939(n) iff n is odd, where A070939(n) = floor(log_2(n)) + 1. - Reinhard Zumkeller, Jan 26 2003
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
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}];
Print[b[[1 ;; 100]]] (* Andres Cicuttin, May 18 2017 *)
(* 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}];
Print[c[[1 ;; 100]]] (* Andres Cicuttin, May 18 2017 *)
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)
a070940 = maximum . a080080_row -- Reinhard Zumkeller, Apr 22 2013
(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
# Yosu Yurramendi, Aug 08 2019
(Python)
def A070940(n):
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
print(n, A070940(n)) # A.H.M. Smeets, Aug 19 2019
(Python)
def A070940(n): return n.bit_length()-(~n&n-1).bit_length() # Chai Wah Wu, Jul 13 2022
CROSSREFS
Bisections give A070941 and this sequence (again).
KEYWORD
nonn,nice,easy,tabf
AUTHOR
N. J. A. Sloane, May 18 2002
EXTENSIONS
Entry revised by Ralf Stephan, Nov 29 2004
STATUS
approved