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

 

Logo

Many excellent designs for a new banner were submitted. We will use the best of them in rotation.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A036989 Read binary expansion of n from the right; keep track of the excess of 1's over 0's that have been seen so far; sequence gives 1 + maximum(excess of 1's over 0's). 5
1, 2, 1, 3, 1, 2, 2, 4, 1, 2, 1, 3, 1, 3, 3, 5, 1, 2, 1, 3, 1, 2, 2, 4, 1, 2, 2, 4, 2, 4, 4, 6, 1, 2, 1, 3, 1, 2, 2, 4, 1, 2, 1, 3, 1, 3, 3, 5, 1, 2, 1, 3, 1, 3, 3, 5, 1, 3, 3, 5, 3, 5, 5, 7, 1, 2, 1, 3, 1, 2, 2, 4, 1, 2, 1, 3, 1, 3, 3, 5, 1, 2, 1, 3, 1, 2, 2, 4, 1, 2, 2, 4, 2, 4, 4, 6, 1, 2, 1, 3, 1, 2, 2, 4, 1 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

Associated with A036988 (Remark 4 of the reference).

REFERENCES

H. Niederreiter and M. Vielhaber, Tree complexity and a doubly ..., J. Complexity, 12 (1996), 187-198.

LINKS

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

H. Niederreiter and M. Vielhaber, Tree Complexity and a Doubly Exponential Gap between Structured and Random Sequences, J. Complexity, 12 (1996), 187-198.

Index entries for sequences related to binary expansion of n

FORMULA

a(n) = 1 iff, in the binary expansion of n, reading from right to left, the number of 1's never exceeds the number of 0's: a(A036990(n)) = 1.

a(0) = 1, a(2n) = max(a(n) - 1, 1), a(2n+1) = a(n) + 1. - Franklin T. Adams-Watters, Dec 26 2006

Equals inverse Moebius transform (A051731) of A010060, the Thue-Morse sequence starting with "1": (1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1,...). - Gary W. Adamson, May 13 2007

EXAMPLE

59 in binary is 111011, excess from right to left is 1,2,1,2,3,4, maximum is 4, so a(59) = 4.

MATHEMATICA

a[0] = 1; a[n_?EvenQ] := a[n] = Max[a[n/2] - 1, 1]; a[n_] := a[n] = a[(n-1)/2] + 1; Table[a[n], {n, 0, 104}] (* Jean-Fran├žois Alcover, Nov 05 2013, after Franklin T. Adams-Watters *)

PROG

(Haskell)

import Data.List (transpose)

a036989 n = a036989_list !! n

a036989_list = 1 : concat (transpose

   [map (+ 1) a036989_list, map ((max 1) . pred) $ tail a036989_list])

-- Reinhard Zumkeller, Jul 31 2013

CROSSREFS

Cf. A036988, A036990, A126387.

Cf. A010060.

Sequence in context: A241165 A233183 A035942 * A035197 A227872 A091948

Adjacent sequences:  A036986 A036987 A036988 * A036990 A036991 A036992

KEYWORD

nonn,easy

AUTHOR

N. J. A. Sloane.

EXTENSIONS

Edited by Joshua Zucker, May 11 2006

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 April 23 13:53 EDT 2014. Contains 240930 sequences.