

A109380


Levenshtein distance between successive factorials when considered as decimal strings.


0



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,4


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


REFERENCES

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


LINKS

Table of n, a(n) for n=0..74.
Michael Gilleland, Levenshtein Distance, in Three Flavors. [It has been suggested that this algorithm gives incorrect results sometimes.  N. J. A. Sloane]


FORMULA

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


EXAMPLE

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.


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


CROSSREFS

Cf. A001358, A081355, A081356, A081230, A109809, A109811.
Sequence in context: A023990 A117894 A177762 * A167754 A011020 A181512
Adjacent sequences: A109377 A109378 A109379 * A109381 A109382 A109383


KEYWORD

easy,nonn,base


AUTHOR

Jonathan Vos Post, Aug 25 2005


EXTENSIONS

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


STATUS

approved



