OFFSET
0,1
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.
FORMULA
a(n) = LD(nameof(n), nameof(n+1)).
EXAMPLE
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.
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]]]
CROSSREFS
KEYWORD
easy,nonn,word
AUTHOR
Jonathan Vos Post, Aug 25 2005
EXTENSIONS
More terms from Robert G. Wilson v, Jan 31 2006
Corrected by Robert Israel, Jan 23 2018
STATUS
approved