|
Search: id:A089591
|
|
|
| A089591 |
|
"Lazy binary" representation of n. Also called redundant binary representation of n. |
|
+0
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; listen)
|
|
|
OFFSET
|
0,3
|
|
|
COMMENT
|
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 signficant 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.
Adjacent sequences: A089588 A089589 A089590 this_sequence A089592 A089593 A089594
Sequence in context: A087486 A102626 A014418 this_sequence A064039 A022100 A041475
|
|
KEYWORD
|
easy,nonn,nice
|
|
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
|
|
|
Search completed in 0.002 seconds
|
