A072998 -id:A072998 - cp's OEIS frontend

A089591 "Lazy binary" representation of n. Also called redundant binary representation of n.

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

Offset: 0

Jeff Erickson, Dec 29 2003

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).
A137951 gives values of terms interpreted as ternary numbers, a(n)=A007089(A137951(n)). - Reinhard Zumkeller, Feb 25 2008

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

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.

R. Zumkeller, Table of n, a(n) for n = 0..10000

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

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

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

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 *)

More terms from R. J. Mathar, Mar 11 2007
Edited by Charles R Greathouse IV, Apr 30 2010
Edited by N. J. A. Sloane, Jun 03 2023

A351702 In the balanced ternary representation of n, reverse the order of digits other than the most significant.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 8, 11, 6, 9, 12, 7, 10, 13, 14, 23, 32, 17, 26, 35, 20, 29, 38, 15, 24, 33, 18, 27, 36, 21, 30, 39, 16, 25, 34, 19, 28, 37, 22, 31, 40, 41, 68, 95, 50, 77, 104, 59, 86, 113, 44, 71, 98, 53, 80, 107, 62, 89, 116, 47, 74, 101, 56, 83, 110, 65, 92

Offset: 0

Kevin Ryde, Feb 19 2022

Self-inverse permutation with swaps confined to terms of a given digit length (A134021) so within blocks n = (3^k+1)/2 .. (3^(k+1)-1)/2.
Can extend to negative n by a(-n) = -a(n).
A072998 is balanced ternary coded in decimal digits so that reversal except first digit of A072998(n) is at A072998(a(n)).  Similarly its ternary equivalent A157671, and also A132141 ternary starting with 1.
These sequences all have a fixed initial digit followed by all ternary strings which is the reversed part.  A007932 is such strings as decimal digits 1,2,3 but it omits the empty string so the whole reversal of A007932(n) is at A007932(a(n+1)-1).
Fixed points a(n) = n are where n in balanced ternary is a palindrome apart from its initial 1.  These are the full balanced ternary palindromes with their least significant 1 removed, so all n = (A134027(m)-1)/3 for m>=2.

			n    = 224 = balanced ternary 1,  0, -1, 1,  0, -1
                      reverse     ^^^^^^^^^^^^^^^^
a(n) = 168 = balanced ternary 1, -1,  0, 1, -1,  0

Cf. A059095 (balanced ternary), A134028 (full reverse), A134027 (palindromes).
Cf. A072998, A157671, A132141, A007932.
In other bases: A059893 (binary), A343150 (Zeckendorf), A343152 (lazy Fibonacci).

a(n) = if(n==0,0, my(k=if(n,logint(n<<1,3)), s=(3^k+1)>>1); s + fromdigits(Vec(Vecrev(digits(n-s,3)),k),3));

cp's OEIS Frontend

A089591 "Lazy binary" representation of n. Also called redundant binary representation of n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Extensions