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

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

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 09:39 EDT 2014. Contains 240961 sequences.