login
Number of numbers that differ from n in ternary representation by exactly one edit-operation: deletion, insertion, or substitution.
0

%I #6 Mar 30 2012 18:50:32

%S 4,6,6,11,10,11,11,11,10,14,15,15,15,14,15,16,16,15,14,15,15,16,15,16,

%T 15,15,14,18,19,19,20,19,20,20,20,19,19,20,20,19,18,19,20,20,19,20,21,

%U 21,21,20,21,20,20,19,18,19,19,20,19,20,20,20,19,20,21,21,20,19,20,21

%N Number of numbers that differ from n in ternary representation by exactly one edit-operation: deletion, insertion, or substitution.

%C a(n) = #{j: LD-3(n,j)=1}, where LD-3 is the Levenshtein distance on ternary strings.

%H Michael 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 n=12: ternary representation of numbers at Levenshtein distance 1 from 12='110':

%e {10, 11, 100, 111, 112, 120, 210, 1010, 1100, 1101,

%e 1102, 1110, 1120, 1210, 2110}, therefore a(12)=15.

%e n=42: ternary representation of numbers at Levenshtein distance 1 from 42='1120':

%e {110, 112, 120, 1020, 1100, 1110, 1121, 1122, 1220,

%e 2120, 10120, 11020, 11120, 11200, 11201, 11202, 11210, 11220, 12120, 21120},

%e therefore a(42)=20.

%Y Cf. A080950, A080910, A007089.

%K nonn,base

%O 0,1

%A _Reinhard Zumkeller_, Apr 06 2003