

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(n1) 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_{k1}, ..., 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 ith digit of a(n) is ceiling( floor( ((n+12^i) mod 2^(i+1))/2^(i1) ) / 2).


REFERENCES

Gerth S. Brodal, Worstcase efficient priority queues, SODA 1996.
Michael J. Clancy and D. E. Knuth, A programming and problemsolving seminar, Technical Report STANCS77606, 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(nhalf1)+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[nhalf1]+1)]]]]; Table[a[n], {n, 0, 100}] (* JeanFranç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



