login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

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
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
Robert Munafo, Alternative Number Formats, section on "Lexicographic Strings".
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
KEYWORD
nonn
EXTENSIONS
Offset corrected by Matthew House, Aug 15 2016
STATUS
approved