A365076 Number of length-n binary words x such that the infinite word xxxx... is balanced.

2, 4, 8, 12, 22, 22, 44, 44, 62, 64, 112, 78, 158, 130, 148, 172, 274, 184, 344, 232, 302, 334, 508, 302, 522, 472, 548, 474, 814, 442, 932, 684, 778, 820, 904, 672, 1334, 1030, 1100, 904, 1642, 904, 1808, 1222, 1282, 1522, 2164, 1198, 2102, 1564, 1912, 1728

Offset: 1

Author

Jeffrey Shallit, Aug 20 2023

Keywords

• nonn

Comments

A binary word w is "balanced" if for all lengths and all blocks b of the same length appearing in it, the number of 1's in b can take only two different values. For example, 00111 is not balanced because 00 has no 1's, 01 has one, and 11 has two.

Examples

			For n = 4, the 12 such words are 0000, 0001, 0010, 0100, 0101, 0111 and their bitwise binary complements.
		

Links

• Laurent Vuillon, Balanced words, Bull. Belg. Math. Soc. Simon Stevin 10(5): 787-805 (December 2003).

Crossrefs

Cf. A057660, A057661.

Programs

Python

from math import gcd
def A365076(n): return sum(n//gcd(n,k) for k in range(1,n+1))+1 # Chai Wah Wu, Aug 24 2023

Python

from math import prod
from sympy import factorint
def A365076(n): return 1+prod((p**((e<<1)+1)+1)//(p+1) for p,e in factorint(n).items()) # Chai Wah Wu, Aug 05 2024

Formula

a(n) = 2*A057661(n).

a(n) = A057660(n) + 1.