|
%I #10 Oct 31 2013 12:17:22
%S 0,1,2,3,3,4,6,8,8,9,10,11,13,16,17,18,19,22,23,26,26,28,30,32,33,35,
%T 37,39,41,43,45,47,49,51,53,55,57,59,61,63,65,67,69,71,73,75,77,79,81,
%U 83,86,88,90,92,94,96,99,101,103,105,107,110,112,114,116,119,121,123,125
%N a(n) is the Levenshtein distance between n and n^n (where each is treated as a string).
%H M. Gilleland, <a href="http://www.merriampark.com/ld.htm">Levenshtein Distance</a>. [It has been suggested that this algorithm gives incorrect results sometimes. - _N. J. A. Sloane_]
%e a(9)=8 since we can transform 9 into 9^9=387420489 by 8 insertions, namely inserting 3,8,7,4,2,0,4 and 8 in front of 9. a(2)=1 since we can transform 2 into 2^2=4 by one substitution, namely 4 for 2.
%t 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 f[n_] := levenshtein[IntegerDigits[n], IntegerDigits[n^n]]; Array[f, 69] (* _Robert G. Wilson v_ *)
%Y Cf. A081231, A081232, A081233, A081234.
%K nonn,base
%O 1,3
%A Francois Jooste (pin(AT)myway.com), Mar 11 2003
%E Corrected by _Robert G. Wilson v_, Jan 25 2006
|
