Number of binary sequences of length $n$

Question

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

Answer 1

Here's one way

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

In English this reads as

The number of aperiodic sequences of length $n$ is $2^n$ minus the number of aperiodic sequences of length $k$ that properly divides $n$

The idea behind this is if we can find the number of length $n$ sequences that are periodic we can find the number of ones that are not, since we know the number of total sequences.

We know that every periodic sequence is composed of some unique aperiodic sequence a number of times and that each of these aperiodic sequences has size $k$ such that $n\mid k$. Thus we are looking for the number of aperiodic sequences sequences of length that divide $n$. This would just be the sum of our function applied to every proper divisor of $n$.

This lends itself to a rather neat little algorithm, which I have implemented in Haskell.

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

Try it online!

The algorithm is not terribly fast because we are still required to factor $n$, so there is definitely room for improvement.

Answer 2

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.