A109382 Levenshtein distance between successive English names of nonnegative integers, excluding spaces and hyphens.
4, 3, 4, 5, 3, 3, 4, 5, 4, 3, 4, 4, 6, 3, 3, 2, 4, 4, 3, 7, 3, 3, 4, 5, 3, 3, 4, 5, 4, 7, 3, 3, 4, 5, 3, 3, 4, 5, 4, 7, 3, 3, 4, 5, 3, 3, 4, 5, 4, 6, 3, 3, 4, 5, 3, 3, 4, 5, 4, 6, 3, 3, 4, 5, 3, 3, 4, 5, 4, 7, 3, 3, 4, 5, 3, 3, 4, 5, 4, 8, 3, 3, 4, 5, 3, 3, 4, 5, 4, 7, 3, 3, 4, 5, 3, 3, 4, 5, 4, 7, 3, 3, 4, 5, 3, 3
Offset: 0
Examples
a(0) = 4 since LD(ZERO,ONE) requires 4 edits. a(1) = 3 since LD(ONE,TWO) which requires 3 substitutions. a(2) = 4 since LD(TWO,THREE) = requires 4 edits (leave the leftmost T unchanged), then 2 substitutions (W to H, O to R), then 2 insertions (E,E). a(4) = 3 as LD(FOUR,FIVE) leaves the leftmost F unchanged, then requires 3 substitutions. From FIVE to SIX leaves the I unchanged. From SIX to SEVEN leaves the S unchanged. From TEN to ELEVEN leaves the EN unchanged. From ELEVEN to TWELVE leaves an E,L,V,E unchanged. From THIRTEEN to FOURTEEN leaves RTEEN unchanged. TWENTYNINE to THIRTY takes 7 edits. THIRTYNINE to FORTY takes 7 edits. SEVENTYNINE to EIGHTY takes 8 edits. EIGHTYNINE to NINETY takes 7 edits. NINETYNINE to ONEHUNDRED takes 7 edits.
Links
- Robert Israel, Table of n, a(n) for n = 0..10000
- Michael Gilleland, Levenshtein Distance, in Three Flavors.
- V. I. Levenshtein, Efficient reconstruction of sequences from their subsequences or supersequences, J. Combin. Theory Ser. A 93 (2001), no. 2, 310-332.
- Landon Curt Noll, The English Name of a Number.
- Robert G. Wilson v, American English names for the numbers from 0 to 100999 without spaces or hyphens.
Programs
-
Maple
with(StringTools): seq(Levenshtein(Select(IsAlpha, convert(n,english)),Select(IsAlpha,convert(n+1,english))),n=0..200); # Robert Israel, Jan 23 2018
-
Mathematica
(* First copy b109382.txt out of A109382 then *) levenshtein[s_List, t_List] := Module[{d, n = Length@s, m = Length@t}, Which[s === t, 0, n == 0, m, m == 0, n, s != t, d = Table[0, {m + 1}, {n + 1}]; d[[1, Range[n + 1]]] = Range[0, n]; d[[Range[m + 1], 1]] = Range[0, m]; Do[ d[[j + 1, i + 1]] = Min[d[[j, i + 1]] + 1, d[[j + 1, i]] + 1, d[[j, i]] + If[ s[[i]] === t[[j]], 0, 1]], {j, m}, {i, n}]; d[[ -1, -1]] ]]; f[x_] := Block[{str = ToString@ lst[[x]], len}, len = StringLength@ str; StringInsert[str, ",", Range[2, len]]]
Formula
a(n) = LD(nameof(n), nameof(n+1)).
Extensions
More terms from Robert G. Wilson v, Jan 31 2006
Corrected by Robert Israel, Jan 23 2018