|
| |
|
|
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; 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 (reinhard.zumkeller(AT)gmail.com), 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 (mathar(AT)strw.leidenuniv.nl), Mar 11 2007
|
|
|
CROSSREFS
| Cf. A000523, A033484, A072998, A024629, A089600, A089601, A089604.
Sequence in context: A102626 A178361 A014418 * A064039 A022100 A041475
Adjacent sequences: A089588 A089589 A089590 * A089592 A089593 A089594
|
|
|
KEYWORD
| easy,nonn,nice,base
|
|
|
AUTHOR
| Jeff Erickson (jeffe(AT)cs.uiuc.edu), Dec 29 2003
|
|
|
EXTENSIONS
| More terms from R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Mar 11 2007
Edited by Charles R Greathouse IV (charles.greathouse(AT)case.edu), Apr 30 2010
|
| |
|
|
