|
Search: id:A070940
|
|
|
| A070940 |
|
Number of digits that must be counted from left to right to reach the last 1 in the binary representation of n. |
|
+0
7
|
|
| 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; listen)
|
|
|
OFFSET
|
1,3
|
|
|
COMMENT
|
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 (reinhard.zumkeller(AT)gmail.com), Jan 26 2003
a(n+1) is the number of distinct values of GCD[2^n,C[n,j]] (or, equivalently, A007814(C(n,j))) arising if j=0,..,n-1. Proof using Kummer's Theorem given by Marc Schwartz. - Labos E., 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 triangle. (Labos)
Smallest x>0 for which a(x)=n equals 2^n. (Labos)
a(n) <= A070939(n), a(n) = A070939(n) iff n is odd, where A070939(n) = floor(log_2(n)) + 1. - Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), Jan 26 2003
|
|
LINKS
|
Index entries for sequences related to binary expansion of n
|
|
FORMULA
|
a(n) = [log2(n)] - A007814(n) = A070939(n) - A007814(n).
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 (reinhard.zumkeller(AT)gmail.com), Feb 01 2003
G.f.: sum(k>=0, t/(1-t^2) * [1 + sum(l>=1, t^2^l)], t=x^2^k). - R. Stephan, Mar 15 2004
|
|
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.
|
|
MAPLE
|
A070940 := n -> if n mod 2 = 0 then A070939(n)-A001511(n/2) else A070939(n); fi;
|
|
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}] (from Robert G. Wilson v Dec 01 2004)
|
|
CROSSREFS
|
Cf. A070939, A001511. Differs from A002487 around 11-th term.
Cf. A000005, A007318, A000079, A082907, A082908.
Bisections give A070941 and this sequence (again).
Sequence in context: A057432 A038568 A071912 this_sequence A020651 A160232 A002487
Adjacent sequences: A070937 A070938 A070939 this_sequence A070941 A070942 A070943
|
|
KEYWORD
|
nonn,nice,easy
|
|
AUTHOR
|
N. J. A. Sloane (njas(AT)research.att.com), May 18 2002
|
|
EXTENSIONS
|
Entry revised by Ralf Stephan, Nov 29 2004
|
|
|
Search completed in 0.003 seconds
|
