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 of all binary 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.