OFFSET
0,1
COMMENTS
a(n) = #{j: LD-3(n,j)=1}, where LD-3 is the Levenshtein distance on ternary strings.
LINKS
Zhuorui He, Table of n, a(n) for n = 0..10000
Michael Gilleland, Levenshtein Distance. [It has been suggested that this algorithm gives incorrect results sometimes. - N. J. A. Sloane]
FORMULA
From Zhuorui He, Oct 01 2025: (Start)
Conjecture: For m >= 3,
a(9m) = a(3m) + 4, a(9m+1) = a(3m) + 5, a(9m+2) = a(3m) + 5,
a(9m+3) = a(3m+1) + 5, a(9m+4) = a(3m+1) + 4, a(9m+5) = a(3m+1) + 5,
a(9m+6) = a(3m+2) + 5, a(9m+7) = a(3m+2) + 5, a(9m+8) = a(3m+2) + 4. (End)
EXAMPLE
n=12: ternary representation of numbers at Levenshtein distance 1 from 12='110': {10, 11, 100, 111, 112, 120, 210, 1010, 1100, 1101, 1102, 1110, 1120, 1210, 2110}, therefore a(12)=15.
n=42: ternary representation of numbers at Levenshtein distance 1 from 42='1120': {110, 112, 120, 1020, 1100, 1110, 1121, 1122, 1220, 2120, 10120, 11020, 11120, 11200, 11201, 11202, 11210, 11220, 12120, 21120}, therefore a(42)=20.
PROG
(Python)
# please run pip install numpy python-baseconv before running this code
import numpy
import baseconv
def A081732(n):
def is_valid(m):
return m[0] != "0" or len(m) == 1
n = baseconv.BaseConverter('012').encode(n)
arr = []
len_n = len(n)
# Deletion
if len_n > 1:
for i in range(len_n):
if is_valid(n[:i]+n[(i+1):]):
arr.append(int(n[:i]+n[(i+1):], 3))
# Insertion
for i in range(len_n+1):
for j in range(3):
if is_valid(n[:i]+str(j)+n[i:]):
arr.append(int(n[:i]+str(j)+n[i:], 3))
# Substitution
for i in range(len_n):
for j in range(3):
if is_valid(n[:i]+str(j)+n[(i+1):]):
arr.append(int(n[:i]+str(j)+n[(i+1):], 3))
return len(numpy.unique(arr)) - 1 # Zhuorui He, Oct 01 2025
CROSSREFS
KEYWORD
nonn,base
AUTHOR
Reinhard Zumkeller, Apr 06 2003
STATUS
approved
