Número de secuencias binarias de longitud $n$

Question

Dejemos que $$p(n) = \#\{f:\mathbb N \to \{0,1\} \mid n \text{ is the shortest period of } f\}$$ es decir $p(n)$ denota el número de secuencias binarias de período exactamente $n$ (y no menos). ¿Hay alguna forma de calcular $p(n)$ ¿sin forzar todas las posibilidades?

Para un $f$ del período $n$ los valores $f(1),f(2),\ldots,f(n)$ ya definen $f$ completamente, así que aquí hay algunas listas de $f$ para los pequeños $n$ (Espero que sea correcto):

$$ \begin{array}{c|l|l} n & \text{list} & p(n) \\ \hline 1 & (0),(1) & 2 \\ \hline 2 & (0,1),(1,0) & 2 \\ \hline 3 & (0,0,1),(0,1,0),(1,0,0),(0,1,1),(1,0,1),(1,1,0) & 6 \\ \hline 4 & (0,0,0,1),(0,0,1,0),(0,1,0,0),(1,0,0,0) & 12 \\ & (1,1,1,0),(1,1,0,1),(1,0,1,1),(0,1,1,1) & \\ & (1,0,0,1),(0,1,1,0) ,(1,1,0,0),(0,0,1,1)& \end{array} $$

Answer 1

La naturaleza de "inclusión-exclusión" del problema, como se menciona en el comentario de mdave16, permite otra fórmula explícita a modo de Inversión de Möbius : $\displaystyle\sum_{d|n} f(d)=2^n$ (ya que el conjunto de todo secuencias binarias de longitud $n$ es la unión de (repeticiones adecuadas de) aquellas cuyo periodo es $d$ sobre todos los divisores $d$ de $n$ ), así que por la fórmula de inversión de Möbius tenemos $\displaystyle f(n)=\sum_{d|n}\mu(d)2^{(n/d)}$ . Aquí $\mu(d)$ es la función de Möbius, que es $0$ a menos que $d$ es libre de cuadrados, y $(-1)^p$ (con $p$ el número de divisores primos de $d$ ) en caso contrario.

Answer 2

Esta es una forma

$$f(n) = 2^n - \sum_{1\leq i<n,n\mid i} f(i)$$

En inglés esto se lee como

El número de secuencias aperiódicas de longitud $n$ es $2^n$ menos el número de secuencias aperiódicas de longitud $k$ que divide adecuadamente $n$

La idea detrás de esto es que si podemos encontrar el número de longitudes $n$ secuencias que son periódicas podemos encontrar el número de las que no lo son, ya que conocemos el número de secuencias totales.

Sabemos que toda secuencia periódica está compuesta por alguna secuencia aperiódica única un número de veces y que cada una de estas secuencias aperiódicas tiene tamaño $k$ tal que $n\mid k$ . Así, buscamos el número de secuencias aperiódicas de longitud que dividen $n$ . Esto sería simplemente la suma de nuestra función aplicada a cada divisor propio de $n$ .

Esto se presta a un pequeño algoritmo bastante ordenado, que he implementado en Haskell.

divisors x = filter ((==0).(mod x)) [1..x-1]
f x=2^x - sum(map f$divisors x)

Pruébelo en línea.

El algoritmo no es terriblemente rápido porque todavía se requiere factorizar $n$ Así que, sin duda, hay margen de mejora.