|
|
A169683
|
|
The canonical skew-binary numbers.
|
|
5
|
|
|
0, 1, 2, 10, 11, 12, 20, 100, 101, 102, 110, 111, 112, 120, 200, 1000, 1001, 1002, 1010, 1011, 1012, 1020, 1100, 1101, 1102, 1110, 1111, 1112, 1120, 1200, 2000, 10000, 10001, 10002, 10010, 10011, 10012, 10020, 10100, 10101, 10102, 10110
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
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.
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.
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.
Popularized by the page numbers in the xkcd book.
Expansion of n in the q-system based on convergents to sqrt(2). [Fraenkel, 1982]. - N. J. A. Sloane, Aug 07 2018
|
|
REFERENCES
|
Chris Okasaki, Purely functional data structures, Cambridge University Press, Pittsburgh, 1999, pp. 76-77.
R. Munroe, xkcd, volume 0, Breadpig, San Francisco, 2009.
|
|
LINKS
|
|
|
FORMULA
|
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
|
|
EXAMPLE
|
The first nonnegative skew-binary numbers (dots denote zeros) are
n : [skew-binary] position of leftmost change
00: [ . . . . . ] -
01: [ . . . . 1 ] 0
02: [ . . . . 2 ] 0
03: [ . . . 1 . ] 1
04: [ . . . 1 1 ] 0
05: [ . . . 1 2 ] 0
06: [ . . . 2 . ] 1
07: [ . . 1 . . ] 2
08: [ . . 1 . 1 ] 0
09: [ . . 1 . 2 ] 0
10: [ . . 1 1 . ] 1
11: [ . . 1 1 1 ] 0
12: [ . . 1 1 2 ] 0
13: [ . . 1 2 . ] 1
14: [ . . 2 . . ] 2
15: [ . 1 . . . ] 3
16: [ . 1 . . 1 ] 0
17: [ . 1 . . 2 ] 0
18: [ . 1 . 1 . ] 1
19: [ . 1 . 1 1 ] 0
20: [ . 1 . 1 2 ] 0
21: [ . 1 . 2 . ] 1
22: [ . 1 1 . . ] 2
23: [ . 1 1 . 1 ] 0
24: [ . 1 1 . 2 ] 0
25: [ . 1 1 1 . ] 1
26: [ . 1 1 1 1 ] 0
27: [ . 1 1 1 2 ] 0
28: [ . 1 1 2 . ] 1
29: [ . 1 2 . . ] 2
30: [ . 2 . . . ] 3
31: [ 1 . . . . ] 4
32: [ 1 . . . 1 ] 0
33: [ 1 . . . 2 ] 0
...
The sequence of positions of the changes appears to be A215020.
(End)
a(2^1-1..2^2-2) = a(0..2^1-1) + 10^0 = [1, 2];
a(2^2-1..2^3-2) = a(0..2^2-1) + 10^1 = [10, 11, 12, 20];
a(2^3-1..2^4-2) = a(0..2^3-1) + 10^2 = [100, 101, 102, 110, 111, 112, 120, 200];
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];
... (End)
|
|
MATHEMATICA
|
f[0] = 0;
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]
f /@ Range[0, 10000]
|
|
PROG
|
(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)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,base
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|