A109380 Levenshtein distance between successive factorials when considered as decimal strings.

0, 1, 1, 2, 2, 1, 3, 3, 5, 1, 4, 5, 7, 7, 9, 9, 10, 12, 13, 14, 12, 12, 16, 15, 17, 16, 19, 16, 21, 24, 21, 22, 22, 25, 25, 25, 27, 32, 33, 30, 34, 34, 36, 36, 37, 38, 38, 44, 42, 44, 42, 46, 47, 48, 50, 50, 47, 52, 52, 49, 54, 60, 60, 59, 56, 60, 62, 68, 70, 65, 65, 67, 70, 70, 74

Offset: 0

Author

Jonathan Vos Post, Aug 25 2005

Keywords

• easy
• nonn
• base

Examples

			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.
		

Links

• Michael Gilleland, Levenshtein Distance, in Three Flavors. [It has been suggested that this algorithm gives incorrect results sometimes. - _N. J. A. Sloane_]
• V. I. Levenshtein, Efficient reconstruction of sequences from their subsequences or supersequences, J. Combin. Theory Ser. A 93 (2001), no. 2, 310-332.

Crossrefs

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

Programs

Mathematica

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 *)

Formula

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

Extensions

Corrected and extended by Robert G. Wilson v, Jan 25 2006