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

 

Logo

The submissions stack has been unacceptably high for several months now. Please voluntarily restrict your submissions and please help with the editing. (We don't want to have to impose further limits.)

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 August 28 10:55 EDT 2015. Contains 261120 sequences.