Let $$p(n) = \#\{f:\mathbb N \to \{0,1\} \mid n \text{ is the shortest period of } f\}$$

that means $p(n)$ denotes the number of binary sequences of period exactly $n$ (and no less). Is there a way to compute $p(n)$ without just bruteforcing all possibilities?

For an $f$ of period $n$ the values $f(1),f(2),\ldots,f(n)$ already define $f$ completely, so here are some lists of such $f$ for small $n$ (I hope it is correct):

$$

\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}

$$

## Best Answer

The "inclusion-exclusion" nature of the problem, as mentioned in mdave16's comment, allows for another, explicit formula by way of

Möbius inversion: $\displaystyle\sum_{d|n} f(d)=2^n$ (since the set ofallbinary sequences of length $n$ is the union of (suitable repetitions of) those whose period is $d$, over all divisors $d$ of $n$), so by the Möbius inversion formula we have $\displaystyle f(n)=\sum_{d|n}\mu(d)2^{(n/d)}$. Here $\mu(d)$ is the Möbius function, which is $0$ unless $d$ is squarefree, and $(-1)^p$ (with $p$ the number of prime divisors of $d$) elsewise.