login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A070940 Number of digits that must be counted from left to right to reach the last 1 in the binary representation of n. 9
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,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 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 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

LINKS

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

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, Feb 01 2003

G.f.: sum(k>=0, t/(1-t^2) * [1 + sum(l>=1, t^2^l)], t=x^2^k). - Ralf 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.

The table starts:

1

1 2

1 3 2 3

1 4 3 4 2 4 3 4

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}] (* Robert G. Wilson v, Dec 01 2004 *)

PROG

(Haskell)

a070940 = maximum . a080080_row  -- Reinhard Zumkeller, Apr 22 2013

CROSSREFS

Cf. A070939, A001511. Differs from A002487 around 11th term.

Cf. A000005, A007318, A000079, A082907, A082908.

Bisections give A070941 and this sequence (again).

Cf. A002064 (row sums), A199570.

Sequence in context: A215467 A038568 A071912 * A020651 A002487 A245328

Adjacent sequences:  A070937 A070938 A070939 * A070941 A070942 A070943

KEYWORD

nonn,nice,easy,tabf

AUTHOR

N. J. A. Sloane, May 18 2002

EXTENSIONS

Entry revised by Ralf Stephan, Nov 29 2004

STATUS

approved

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

Content is available under The OEIS End-User License Agreement .

Last modified August 30 07:52 EDT 2015. Contains 261200 sequences.