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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A089591 "Lazy binary" representation of n. Also called redundant binary representation of n. 5
0, 1, 10, 11, 20, 101, 110, 111, 120, 201, 210, 1011, 1020, 1101, 1110, 1111, 1120, 1201, 1210, 2011, 2020, 2101, 2110, 10111, 10120, 10201, 10210, 11011, 11020, 11101, 11110, 11111, 11120, 11201, 11210, 12011, 12020, 12101, 12110, 20111 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

Replacing "if" by "while" in the definition gives standard binary (A007088).

a(2n+1) = a(n):1 and a(2n+2) = b(n):0, where b(n) is obtained from a(n) by incrementing the least significant digit and : denotes string concatenation.

Every pair of 2's is separated by a 0 and every pair of significant 0's is separated by a 2.

a(n) has exactly floor(lg((n+2)/3))+1 digits [cf. A033484] and their sum is exactly floor(lg(n+1)) [A000523].

The i-th digit of a(n) is ceiling( floor( ((n+1-2^i) mod 2^(i+1))/2^(i-1) ) / 2).

A137951 gives values of terms interpreted as ternary numbers, a(n)=A007089(A137951(n)). - Reinhard Zumkeller, Feb 25 2008

REFERENCES

Gerth S. Brodal. Worst-case efficient priority queues. SODA 1996.

Michael J. Clancy and D. E. Knuth. A programming and problem-solving seminar. Technical Report STAN-CS-77-606, Department of Computer Science, Stanford University, Palo Alto, 1977.

Haim Kaplan and Robert E. Tarjan. Purely functional representations of catenable sorted lists. STOC 1996.

Chris Okasaki. Purely Functional Data Structures. Cambridge, 1998.

LINKS

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

FORMULA

Let a(0) = 0 and construct a(n) from a(n-1) by (i) incrementing the rightmost digit and (ii) if any digit is 2, replace the rightmost 2 with a 0 and increment the digit immediately to its left.

EXAMPLE

a(8) = 120 -> 121 -> 201 = a(9); a(9) = 201 -> 202 -> 210 = a(10).

MAPLE

A089591 := proc(n) option remember ; local nhalf ; if n <= 1 then RETURN(n) ; else nhalf := floor(n/2) ; if n mod 2 = 1 then RETURN(10*A089591(nhalf) +1) ; else RETURN(10*(A089591(nhalf-1)+1)) ; fi ; fi ; end: for n from 0 to 200 do printf("%d, ", A089591(n)) ; od ; # R. J. Mathar, Mar 11 2007

MATHEMATICA

a[n_] := a[n] = Module[{nhalf}, If[n <= 1, Return[n], nhalf = Floor[n/2]; If[Mod[n, 2]==1, Return[10*a[nhalf]+1], Return[10*(a[nhalf-1]+1)]]]]; Table[a[n], {n, 0, 100}] (* Jean-Fran├žois Alcover, Jan 19 2016, after R. J. Mathar *)

CROSSREFS

Cf. A000523, A033484, A072998, A024629, A089600, A089601, A089604.

Sequence in context: A102626 A178361 A014418 * A064039 A255536 A277588

Adjacent sequences:  A089588 A089589 A089590 * A089592 A089593 A089594

KEYWORD

easy,nonn,nice,base

AUTHOR

Jeff Erickson, Dec 29 2003

EXTENSIONS

More terms from R. J. Mathar, Mar 11 2007

Edited by Charles R Greathouse IV, Apr 30 2010

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 October 24 06:43 EDT 2017. Contains 293836 sequences.