login
This site is supported by donations to The OEIS Foundation.

 

Logo


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

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]

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

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
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 23 13:53 EDT 2019. Contains 326227 sequences. (Running on oeis4.)