A010097 Prefix (or Levenshtein) codes for natural numbers.

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

Offset

0,2

References

D. E. Knuth, "Supernatural Numbers", in D. A. Klarner, editor, The Mathematical Gardner. Prindle, Weber and Schmidt, Boston, 1981, pp. 310-325.

D. E. Knuth, Selected Papers on Fun and Games, CSLI, 2011.

R. E. Krichevsky, Szhatie i poisk informatsii (Compressing and searching for information), Moscow, 1988, ISBN 5-256-00325-9.

Links

Matthew House, Table of n, a(n) for n = 0..10000

Robert Munafo, Alternative Number Formats, section on "Lexicographic Strings".

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.

Prog

(Python)
def encode(n):
    if n == 0: return "0"
    c, C = "", 1
    while n > 0:
        b = bin(n)[3:]
        c = b + c
        if (m := len(b)) > 0: C += 1
        n = m
    c = "1" * C + "0" + c
    return c
a = lambda n: int(encode(n), 2) # Darío Clavijo, Aug 23 2024
(PARI) apply( {A010097(n)=if(n, n+2^(n=exponent(n))*((n=A010097(n))+2<<exponent(n+!n)-1))}, [0..44]) \\ M. F. Hasler, Oct 24 2024

Crossrefs

Knuth articles also give A000918 and A171885.

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