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