

A010097


Prefix (or Levenshtein) codes for natural numbers.


2



0, 2, 12, 13, 112, 113, 114, 115, 232, 233, 234, 235, 236, 237, 238, 239, 3840, 3841, 3842, 3843, 3844, 3845, 3846, 3847, 3848, 3849, 3850, 3851, 3852, 3853, 3854, 3855, 7712, 7713, 7714, 7715
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


REFERENCES

R. E. Krichevsky, Szhatie i poisk informatsii (Compressing and searching for information), Moscow, 1988, ISBN 5256003259.
D. E. Knuth, "Supernatural Numbers", in D. A. Klarner, editor, The Mathematical Gardner. Prindle, Weber and Schmidt, Boston, 1981, pp. 310325. [Robert Munafo, Mar 19 2010]
D. E. Knuth, Selected Papers on Fun and Games, to be published (later in 2010). [Robert Munafo, Mar 19 2010]


LINKS

Matthew House, Table of n, a(n) for n = 0..10000
R. Munafo, Alternative Number Formats, section on "Lexicographic Strings". [Robert Munafo, Mar 19 2010]
Wikipedia, Levenshtein coding


FORMULA

The code for n is found as follows: from right to left, the truncated (without the leading 1) binary representations of n, floor(log_2(n)), floor(log_2(floor(log_2(n)))), etc., are written as long as they consist of at least one bit; then we write a 0 followed by log*(n) 1's.


CROSSREFS

Knuth articles also give A000918 and A171885. [Robert Munafo, Mar 19 2010]
Sequence in context: A072483 A081539 A141273 * A103761 A286241 A078755
Adjacent sequences: A010094 A010095 A010096 * A010098 A010099 A010100


KEYWORD

nonn


AUTHOR

Leonid Broukhis


EXTENSIONS

Offset corrected by Matthew House, Aug 15 2016


STATUS

approved



