cp's OEIS Frontend

A169683 The canonical skew-binary numbers.

%I A169683 #42 May 16 2022 10:02:07
%S A169683 0,1,2,10,11,12,20,100,101,102,110,111,112,120,200,1000,1001,1002,
%T A169683 1010,1011,1012,1020,1100,1101,1102,1110,1111,1112,1120,1200,2000,
%U A169683 10000,10001,10002,10010,10011,10012,10020,10100,10101,10102,10110
%N A169683 The canonical skew-binary numbers.
%C A169683 Skew-binary is a positional system in which the n-th digit has weight 2^n-1, using digits 0, 1 and 2. In canonical form only the least significant nonzero digit is allowed to be 2.
%C A169683 The numbers can also be obtained as successive states of a counter: start at 0; increment by adding 1 to last digit, except if the current state ends with ...,x,2,0,...,0 with k trailing zeros, the next state is ...,x+1,0,0,...0 with k+1 trailing zeros.
%C A169683 Incrementing and decrementing numbers in this system can be done in O(1) since an increment will affect at most the two least significant nonzero digits and not carry through the entire number.
%C A169683 Popularized by the page numbers in the xkcd book.
%C A169683 Expansion of n in the q-system based on convergents to sqrt(2). [Fraenkel, 1982]. - _N. J. A. Sloane_, Aug 07 2018
%D A169683 Chris Okasaki, Purely functional data structures, Cambridge University Press, Pittsburgh, 1999, pp. 76-77.
%D A169683 R. Munroe, xkcd, volume 0, Breadpig, San Francisco, 2009.
%H A169683 Martin Büttner, <a href="/A169683/b169683.txt">Table of n, a(n) for n = 0..10000</a> (terms up to a(110) from N. J. A. Sloane)
%H A169683 A. S. Fraenkel, <a href="http://www.jstor.org/stable/2321643">How to beat your Wythoff games' opponent on three fronts</a>, Amer. Math. Monthly, 89 (1982), 353-361. See Table 2.
%H A169683 E. W. Myers, <a href="http://dx.doi.org/10.1016/0020-0190(83)90106-0">An applicative random-access stack</a>, Information Processing Letters 17.5, 1983, pages 241-248.
%H A169683 Wikipedia, <a href="http://en.wikipedia.org/wiki/Skew_binary_number_system">Skew binary number system</a>
%F A169683 a(0) = 0; for n >= 1, a(2^n-1+i) = a(i) + 10^(n-1) for 0 <= i <= 2^n-1. - _Jianing Song_, May 16 2022
%e A169683 From _Joerg Arndt_, May 27 2016: (Start)
%e A169683 The first nonnegative skew-binary numbers (dots denote zeros) are
%e A169683 n :  [skew-binary]  position of leftmost change
%e A169683 00:  [ . . . . . ]  -
%e A169683 01:  [ . . . . 1 ]  0
%e A169683 02:  [ . . . . 2 ]  0
%e A169683 03:  [ . . . 1 . ]  1
%e A169683 04:  [ . . . 1 1 ]  0
%e A169683 05:  [ . . . 1 2 ]  0
%e A169683 06:  [ . . . 2 . ]  1
%e A169683 07:  [ . . 1 . . ]  2
%e A169683 08:  [ . . 1 . 1 ]  0
%e A169683 09:  [ . . 1 . 2 ]  0
%e A169683 10:  [ . . 1 1 . ]  1
%e A169683 11:  [ . . 1 1 1 ]  0
%e A169683 12:  [ . . 1 1 2 ]  0
%e A169683 13:  [ . . 1 2 . ]  1
%e A169683 14:  [ . . 2 . . ]  2
%e A169683 15:  [ . 1 . . . ]  3
%e A169683 16:  [ . 1 . . 1 ]  0
%e A169683 17:  [ . 1 . . 2 ]  0
%e A169683 18:  [ . 1 . 1 . ]  1
%e A169683 19:  [ . 1 . 1 1 ]  0
%e A169683 20:  [ . 1 . 1 2 ]  0
%e A169683 21:  [ . 1 . 2 . ]  1
%e A169683 22:  [ . 1 1 . . ]  2
%e A169683 23:  [ . 1 1 . 1 ]  0
%e A169683 24:  [ . 1 1 . 2 ]  0
%e A169683 25:  [ . 1 1 1 . ]  1
%e A169683 26:  [ . 1 1 1 1 ]  0
%e A169683 27:  [ . 1 1 1 2 ]  0
%e A169683 28:  [ . 1 1 2 . ]  1
%e A169683 29:  [ . 1 2 . . ]  2
%e A169683 30:  [ . 2 . . . ]  3
%e A169683 31:  [ 1 . . . . ]  4
%e A169683 32:  [ 1 . . . 1 ]  0
%e A169683 33:  [ 1 . . . 2 ]  0
%e A169683 ...
%e A169683 The sequence of positions of the changes appears to be A215020.
%e A169683 (End)
%e A169683 From _Jianing Song_, May 16 2022: (Start)
%e A169683 a(2^1-1..2^2-2) = a(0..2^1-1) + 10^0 = [1, 2];
%e A169683 a(2^2-1..2^3-2) = a(0..2^2-1) + 10^1 = [10, 11, 12, 20];
%e A169683 a(2^3-1..2^4-2) = a(0..2^3-1) + 10^2 = [100, 101, 102, 110, 111, 112, 120, 200];
%e A169683 a(2^4-1..2^5-2) = a(0..2^4-1) + 10^3 = [1000, 1001, 1002, 1010, 1011, 1012, 1020, 1100, 1101, 1102, 1110, 1111, 1112, 1120, 1200, 2000];
%e A169683 ... (End)
%t A169683 f[0] = 0;
%t A169683 f[n_] := Module[{m = Floor@Log2[n + 1], d = n, pos}, Reap[While[m > 0, pos = 2^m - 1; Sow @ Floor[d/pos]; d = Mod[d, pos]; --m;]][[2, 1]] // FromDigits]
%t A169683 f /@ Range[0, 10000]
%o A169683 (PARI) A169683(lim) = my(v=vector(1<<lim-1)); v[1] = 0; for(n=1, lim-1, for(i=0, 1<<n-1, v[1<<n+i] = v[i+1]+10^(n-1))); v \\ _Jianing Song_, May 16 2022, gives a(0..2^lim-2)
%K A169683 nonn,base
%O A169683 0,3
%A A169683 _N. J. A. Sloane_, Apr 13 2010
%E A169683 Definition edited by _Martin Büttner_, Jun 10 2015