A394359 - OEIS

A394359

a(n) is the number of distinct tuples of n Hamming distances between a binary string of length n and consecutive substrings of a binary string of length 2n - 1.

%I #20 Mar 18 2026 05:27:24

%S 2,9,48,297,2040,15425,125232,1070553,9530752,86526701,800164636,

%T 7368225813,68065405520,586441789081

%N a(n) is the number of distinct tuples of n Hamming distances between a binary string of length n and consecutive substrings of a binary string of length 2n - 1.

%C a(n) <= 2^(3n-2), which is the number of pairs of binary strings upto simultaneous inverting their bits.

%C a(n) <= (n+1)^n, which is the number of tuples of n integers from the interval [0,n].

%C a(n) >= 2^n, which is achieved on the first string being all-zeros and different second strings starting with n-1 zeros.

%H user9206 et al., <a href="https://codegolf.stackexchange.com/q/113785">Count the number of Hamming distance sequences</a>, CodeGolf, 2017.

%e For n = 2, all pairs of integers from [0,2] are achievable as Hamming distances, hence a(2) = 3^2 = 9.

%K nonn,more

%O 1,1

%A _Max Alekseyev_, Mar 17 2026

%E a(13)-a(14) from _Hugo Pfoertner_, Mar 17 2026, found with user feersum's C++ program from the CodeGolf challenge.