0,4

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 Levenshtein, who developed this metric in 1965. Levenshtein distance is a generalization of Hamming distance.

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

Michael Gilleland, Levenshtein Distance, in Three Flavors. [It has been suggested that this algorithm gives incorrect results sometimes. - N. J. A. Sloane (njas(AT)research.att.com)]

a(n) = LD(n!,(n+1)!)

a(0) = 0 since LD(0!,1!) = LD(1,1) which requires 0 edits.

a(1) = 1 since LD(1!,2!) = LD(1,2) which requires 1 substitution.

a(2) = 1 since LD(2!,3!) = LD(2,6) which requires 1 substitution.

a(3) = 2 since LD(3!,4!) = LD(6,24) which requires 1 substitution and 1 insertion.

a(4) = 2 since LD(4!,5!) = LD(24,120) which requires 1 insertion (1 to the left of 2) and 1 substitution (from 4 to 0).

a(5) = 1 since LD(5!,6!) = LD(120,720) which requires 1 substitution (from 1 to 7).

a(6) = 3 since LD(6!,7!) = LD(720,5040) which requires 1 substitution (from 7 to 5), then 2 insertions (0 to right of 7, 4 to right of 7) and leaving the rightmost digit unedited.

a(7) = 3 as it takes a minimum of 3 edits to get from 5040 to 40320.

a(8) = 5 since LD(8!,9!) = LD(40320,362880) which requires 5 edits.

a(9) = 1 since LD(9!,10!) = LD(362880,3628800) which requires 1 insertion of a zero.

a(10) = 4 since LD(10!,11!) = LD(3628800,39916800) which takes 4 edits.

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[n_] := levenshtein[IntegerDigits[n! ], IntegerDigits[(n + 1)! ]]; Table[ f[n], {n, 0, 74}] (* Robert G. Wilson v *).

Cf. A001358, A081355, A081356, A081230, A109809, A109811.

Sequence in context: A109524 A023990 A117894 this_sequence A167754 A011020 A076019

Adjacent sequences: A109377 A109378 A109379 this_sequence A109381 A109382 A109383

easy,nonn

Jonathan Vos Post (jvospost3(AT)gmail.com), Aug 25 2005

Corrected and extended by Robert G. Wilson v (rgwv(at)rgwv.com), Jan 25 2006