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.

2, 9, 48, 297, 2040, 15425, 125232, 1070553, 9530752, 86526701, 800164636, 7368225813, 68065405520, 586441789081

Offset

1,1

Comments

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

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

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

Links

Table of n, a(n) for n=1..14.

user9206 et al., Count the number of Hamming distance sequences, CodeGolf, 2017.

Example

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

Crossrefs

Sequence in context: A368961 A100427 A214404 * A074143 A198892 A357790

Adjacent sequences: A394356 A394357 A394358 * A394360 A394361 A394362

Keyword

nonn,more

Author

Max Alekseyev, Mar 17 2026

Extensions

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

Status

approved