|
| |
|
|
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
|
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. (Note that changing "if" to "while" in this recipe gives the standard binary representation of n, A007088(n)).
Equivalently, 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.
If the digits of a(n) are d_k, d_{k-1}, ..., d_2, d_1, d_0, then n = Sum_{i=0..k} d_i*2^i, just as in standard binary notation. The difference is that here we are a bit lazy, and allow a few digits to be 2's. The number of 2's in a(n) appears to be A037800(n+1). - N. J. A. Sloane, Jun 03 2023
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(log_2((n+2)/3))+1 digits [cf. A033484] and their sum is exactly floor(log_2(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).
|
|
|
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
|
|
|
|
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
|
A158582: lazy binary different from regular binary, A089633: lazy binary and regular binary agree.
|
|
|
KEYWORD
|
easy,nonn,nice,base
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
