login
This site is supported by donations to The OEIS Foundation.

 

Logo

Many excellent designs for a new banner were submitted. We will use the best of them in rotation.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A109382 Levenshtein distance between successive English names of nonnegative integers, excluding spaces and hyphens. 3
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, 4, 5, 3, 3 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,1

COMMENTS

The Levenshtein distance (also called edit distance) between two strings is equal to the minimum number of insertion, deletion, or substitution operations needed to transform one string into the other. It is named after the Russian scientist Vladimir I. Levenshtein, who developed this metric in 1965. Levenshtein distance is a generalization of Hamming distance. The Levenshtein distance has several simple upper and lower bounds, particularly for this sequence, it is always at least the difference of the sizes of the two strings. Hence LD(name of n, name of n+1) is >= | A005589(n)-A005589(n+1) |, since A005589 is "Number of letters in the English name of n, excluding spaces and hyphens."

REFERENCES

V. I. Levenshtein, Efficient reconstruction of sequences from their subsequences or supersequences, J. Combin. Theory Ser. A 93 (2001), no. 2, 310-332.

LINKS

Table of n, a(n) for n=0..104.

Michael Gilleland, Levenshtein Distance, in Three Flavors.

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.

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

Cf. A001477, A005589, A081355, A081356, A081230, A109809, A109811.

Sequence in context: A204818 A099634 A203144 * A090369 A132293 A205398

Adjacent sequences:  A109379 A109380 A109381 * A109383 A109384 A109385

KEYWORD

easy,nonn,word

AUTHOR

Jonathan Vos Post, Aug 25 2005

EXTENSIONS

More terms from Robert G. Wilson v, Jan 31 2006

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified April 24 05:31 EDT 2014. Contains 240953 sequences.