A366916 - OEIS

%I #41 Nov 08 2023 11:16:36

%S 2,2,2,3,4,5,6,8,9,11,15,18,22,30,35,43,57,69,88,114,142,177,227

%N Maximum number of codewords in a binary Herbert code of length n that corrects two deletions.

%C The maximum number of codewords for different N in Helberg code for two deletion binary Helberg code.

%H K. A. S. Abdel-Ghaffar, F. Paluncic, H. C. Ferreira and W. A. Clarke, <a href="https://doi.org/10.1109/TIT.2011.2174961">On Helberg's Generalization of the Levenshtein Code for Multiple Deletion/Insertion Error Correction</a>, IEEE Transactions on Information Theory, vol. 58, no. 3, pp. 1804-1808, March 2012, doi: 10.1109/TIT.2011.2174961. See also <a href="https://www.researchgate.net/publication/260541992_On_Helberg&#39;s_Generalization_of_the_Levenshtein_Code_for_Multiple_DeletionInsertion_Error_Correction">on ResearchGate</a>.

%e For N = 4, using the Helberg formula Equation 2 in the reference paper, we will get different values of 'a' for different codewords. Now, the maximum number of codewords for a particular 'a' will be 2 in this example.

%e The same formula is used to calculate 'a' and then the maximum number of codewords for different values of N.

%e Note: The first term will be obtained by applying the Helberg formula (Equation 2) with an offset of three. The first term will be calculated as a(3)=2.

%o (Python)

%o import numpy as np

%o import sys

%o def String_generate(n, k, x, final_list):

%o     if n == 0:

%o         final_list.append(x[:])

%o     else:

%o         for j in range(0, k):

%o             x.append(j)

%o             String_generate(n-1, k, x, final_list)

%o             x.pop()

%o     return x

%o def Vi_generate(n, s, v):

%o     for i in range(0, n):

%o         for j in range(1, s+1):

%o             v[i] += v[i-j] if (i-j >= 0) else 0

%o def find_M(v, s, n):

%o     m = 1

%o     for i in range(1, s+1):

%o         m += v[n-i]

%o     return m

%o def func(num, v, m, n, ans):

%o     sum = 0

%o     for i in range(0, n):

%o         sum += v[i]*num[i]

%o     sum = sum % m

%o     if sum not in ans:

%o         ans[sum] = []

%o     ans[sum].append(num)

%o def a(n):

%o     x = []

%o     final_list = []

%o     q = 2

%o     s = 2

%o     v = np.ones(n)

%o     ans = {}

%o     if s < n:

%o         String_generate(n, q, x, final_list)

%o         x = final_list

%o         x = np.array(x)

%o         Vi_generate(n, s, v)

%o         m = find_M(v, s, n)

%o         for i in x:

%o             func(i, v, m, n, ans)

%o     else:

%o         ans[0] = []

%o     return max(len(v) for v in ans.values())

%K nonn,more

%O 3,1

%A _Devdeep Shetranjiwala_ and Manish Gupta, Oct 28 2023