cp's OEIS Frontend

A010097 Prefix (or Levenshtein) codes for natural numbers.

%I A010097 #32 Oct 25 2024 09:31:34
%S A010097 0,2,12,13,112,113,114,115,232,233,234,235,236,237,238,239,3840,3841,
%T A010097 3842,3843,3844,3845,3846,3847,3848,3849,3850,3851,3852,3853,3854,
%U A010097 3855,7712,7713,7714,7715
%N A010097 Prefix (or Levenshtein) codes for natural numbers.
%D A010097 D. E. Knuth, "Supernatural Numbers", in D. A. Klarner, editor, The Mathematical Gardner. Prindle, Weber and Schmidt, Boston, 1981, pp. 310-325.
%D A010097 D. E. Knuth, Selected Papers on Fun and Games, CSLI, 2011.
%D A010097 R. E. Krichevsky, Szhatie i poisk informatsii (Compressing and searching for information), Moscow, 1988, ISBN 5-256-00325-9.
%H A010097 Matthew House, <a href="/A010097/b010097.txt">Table of n, a(n) for n = 0..10000</a>
%H A010097 Robert Munafo, <a href="http://mrob.com/pub/math/altnum.html#lexi">Alternative Number Formats</a>, section on "Lexicographic Strings".
%H A010097 Wikipedia, <a href="https://en.wikipedia.org/wiki/Levenshtein_coding">Levenshtein coding</a>
%F A010097 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.
%o A010097 (Python)
%o A010097 def encode(n):
%o A010097     if n == 0: return "0"
%o A010097     c, C = "", 1
%o A010097     while n > 0:
%o A010097         b = bin(n)[3:]
%o A010097         c = b + c
%o A010097         if (m := len(b)) > 0: C += 1
%o A010097         n = m
%o A010097     c = "1" * C + "0" + c
%o A010097     return c
%o A010097 a = lambda n: int(encode(n),2) # _Darío Clavijo_, Aug 23 2024
%o A010097 (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
%Y A010097 Knuth articles also give A000918 and A171885.
%K A010097 nonn
%O A010097 0,2
%A A010097 _Leonid Broukhis_
%E A010097 Offset corrected by _Matthew House_, Aug 15 2016