login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A169683 The canonical skew-binary numbers. 2
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.

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

N. J. A. Sloane and Martin Büttner, Table of n, a(n) for n = 0..10000 (terms up to a(110) by N. J. A. Sloane)

E. W. Myers, An applicative random-access stack, Information Processing Letters 17.5, 1983, pages 241-248.

Wikipedia, Skew binary number system

EXAMPLE

From Joerg Arndt, May 27 2016: (Start)

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)

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]

CROSSREFS

Sequence in context: A136819 A136816 A188264 * A134948 A060045 A000462

Adjacent sequences:  A169680 A169681 A169682 * A169684 A169685 A169686

KEYWORD

nonn

AUTHOR

N. J. A. Sloane, Apr 13 2010

EXTENSIONS

Definition edited by Martin Büttner, Jun 10 2015

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified April 24 00:59 EDT 2017. Contains 285338 sequences.