This site is supported by donations to The OEIS Foundation.

Annual Appeal: Please make a donation (tax deductible in USA) to keep the OEIS running. Over 5000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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, 310-332. LINKS 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

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