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

 

Logo

Annual Appeal: Please make a donation (tax deductible in USA) to keep the OEIS running. Over 5000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".

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 | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified December 4 15:24 EST 2016. Contains 278750 sequences.