login
"Lazy binary" representation of n. Also called redundant binary representation of n.
5

%I #30 Jun 03 2023 21:42:35

%S 0,1,10,11,20,101,110,111,120,201,210,1011,1020,1101,1110,1111,1120,

%T 1201,1210,2011,2020,2101,2110,10111,10120,10201,10210,11011,11020,

%U 11101,11110,11111,11120,11201,11210,12011,12020,12101,12110,20111

%N "Lazy binary" representation of n. Also called redundant binary representation of n.

%C 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)).

%C 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.

%C 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

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

%C 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].

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

%C A137951 gives values of terms interpreted as ternary numbers, a(n)=A007089(A137951(n)). - _Reinhard Zumkeller_, Feb 25 2008

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

%D 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.

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

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

%H R. Zumkeller, <a href="/A089591/b089591.txt">Table of n, a(n) for n = 0..10000</a>

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

%p 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

%t 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_ *)

%Y Cf. A000523, A033484, A072998, A024629, A089600, A089601, A089604, A037800.

%Y A158582: lazy binary different from regular binary, A089633: lazy binary and regular binary agree.

%K easy,nonn,nice,base

%O 0,3

%A _Jeff Erickson_, Dec 29 2003

%E More terms from _R. J. Mathar_, Mar 11 2007

%E Edited by _Charles R Greathouse IV_, Apr 30 2010

%E Edited by _N. J. A. Sloane_, Jun 03 2023