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

Author

Leonid Broukhis

Keywords

• nonn

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

Crossrefs

Knuth articles also give A000918 and A171885.

Programs

PARI

apply( {A010097(n)=if(n, n+2^(n=exponent(n))*((n=A010097(n))+2<M. F. Hasler, Oct 24 2024

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

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.

Extensions

Offset corrected by Matthew House, Aug 15 2016