cp's OEIS Frontend

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

%I A109380 #20 Aug 05 2025 22:56:01
%S A109380 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,
%T A109380 21,24,21,22,22,25,25,25,27,32,33,30,34,34,36,36,37,38,38,44,42,44,42,
%U A109380 46,47,48,50,50,47,52,52,49,54,60,60,59,56,60,62,68,70,65,65,67,70,70,74
%N A109380 Levenshtein distance between successive factorials when considered as decimal strings.
%H A109380 Michael Gilleland, <a href="https://people.cs.pitt.edu/~kirk/cs1501/Pruhs/Spring2006/assignments/editdistance/Levenshtein%20Distance.htm">Levenshtein Distance, in Three Flavors</a>. [It has been suggested that this algorithm gives incorrect results sometimes. - _N. J. A. Sloane_]
%H A109380 V. I. Levenshtein, <a href="https://doi.org/10.1006/jcta.2000.3081">Efficient reconstruction of sequences from their subsequences or supersequences</a>, J. Combin. Theory Ser. A 93 (2001), no. 2, 310-332.
%F A109380 a(n) = LD(n!,(n+1)!).
%e A109380 a(0) = 0 since LD(0!,1!) = LD(1,1) which requires 0 edits.
%e A109380 a(1) = 1 since LD(1!,2!) = LD(1,2) which requires 1 substitution.
%e A109380 a(2) = 1 since LD(2!,3!) = LD(2,6) which requires 1 substitution.
%e A109380 a(3) = 2 since LD(3!,4!) = LD(6,24) which requires 1 substitution and 1 insertion.
%e A109380 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).
%e A109380 a(5) = 1 since LD(5!,6!) = LD(120,720) which requires 1 substitution (from 1 to 7).
%e A109380 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.
%e A109380 a(7) = 3 as it takes a minimum of 3 edits to get from 5040 to 40320.
%e A109380 a(8) = 5 since LD(8!,9!) = LD(40320,362880) which requires 5 edits.
%e A109380 a(9) = 1 since LD(9!,10!) = LD(362880,3628800) which requires 1 insertion of a zero.
%e A109380 a(10) = 4 since LD(10!,11!) = LD(3628800,39916800) which takes 4 edits.
%t A109380 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]] ]];
%t A109380 f[n_] := levenshtein[IntegerDigits[n! ], IntegerDigits[(n + 1)! ]]; Table[ f[n], {n, 0, 74}] (* _Robert G. Wilson v_ *)
%Y A109380 Cf. A001358, A081355, A081356, A081230, A109809, A109811.
%K A109380 easy,nonn,base
%O A109380 0,4
%A A109380 _Jonathan Vos Post_, Aug 25 2005
%E A109380 Corrected and extended by _Robert G. Wilson v_, Jan 25 2006