Em Português: Seja $n$ um natural fixado. Dizemos que uma sequência $(x_1 , ..., x_n)$ tal que $x_j \in \{ 0,1\}$ para $1 \leq j \leq n$ é aperiódica se não existir divisor $0 < d < n$ tal que a sequência seja formada pela justaposição de $\frac{n}{d}$ cópias do bloco $(x_1 , ..., x_d)$. Calcule, em função de $n$, o número de sequências aperiódica como acima.
English: Let $n$ be a fixed natural number. We say that a sequence $(x_1,...,x_n)$ such that $x_j\in \{ 0,1 \}$ for $1\leq j\leq n$ is aperiodic if there is no divisor $0<d<n$ such that the sequence is formed by the juxtaposition of $\frac{n}{d}$ copies of the block $(x_1, ..., x_d) $. Calculate, as a function of $n$, the number of aperiodic sequences as above.
Let $a_n$ be the number of aperiodic sequences of length $n$. Note that $a_1=2$, since the sequences $0$ and $1$ are vacuously aperiodic.
Suppose that $\sigma$ is a periodic sequence of length $n$, of minimal period $d$. Let $\beta$ be the periodic block of length $d$; then $\beta$ is an aperiodic sequence of length $d$. Conversely, if $0<d<n$, and $d\mid n$, then for each aperiodic sequence $\beta$ of length $d$ the sequence
$$\underbrace{\beta\beta\ldots\beta}_{n/d\text{ times}}$$
is a periodic sequence of length $n$ and minimal period $d$. It follows that there are
$$\sum\{a_d:0<d<n\text{ and }d\mid n\}$$
periodic sequences of length $n$ and hence that
$$a_n=2^n-\sum\{a_d:0<d<n\text{ and }d\mid n\}\;.\tag{0}$$
Let $p$ be any prime. Then $$a_{p^n}=2^{p^n}-\sum_{k=0}^{n-1}a_{p^k}\;,\tag{1}$$
and calculating a few values is very instructive:
$$\begin{array}{cc} 0&1&2&3\\ 2&2^p-2&2^{p^2}-2^p&2^{p^3}-2^{p^2} \end{array}$$
This leads immediately to the conjecture that $$a_{p^n}=2^{p^n}-2^{p^{n-1}}$$ for $n>0$, and the conjecture is easily proved by induction using $(1)$.
More generally, suppose that $n=p_1^{r_1}\ldots p_m^{r_m}$, where $p_1,\ldots,p_m$ are distinct primes and $r_1,\ldots,r_m\ge 1$. Form the product
$$\prod_{k=1}^mp_k^{r_k-1}(p_k-1)=\left(\prod_{k=1}^mp_k^{r_k-1}\right)\prod_{k=1}^m(p_k-1)=\left(\prod_{k=1}^mp_k^{r_k-1}\right)\sum_{S\subseteq[m]}(-1)^{m-|S|}\prod_{k\in S}p_k\;.$$
For each $S\subseteq[m]$ let
$$\alpha_S=\left(\prod_{k=1}^mp_k^{r_k-1}\right)\prod_{k\in S}p_k\;;$$
then
$$a_n=\sum_{S\subseteq[m]}(-1)^{m-|S|}2^{\alpha_S}\;.\tag{2}$$
For example, if $p$ and $q$ are distinct primes,
$$a_{p^2q^2}=2^{\alpha_{\{p,q\}}}-2^{\alpha_{\{p\}}}-2^{\alpha_{\{q\}}}+2^{\alpha_\varnothing}=2^{p^2q^2}-2^{p^2q}-2^{pq^2}+2^{pq}\;.$$
You can probably prove this by induction using $(0)$, but it’s easier to see it as the result of an inclusion-exclusion argument. Rather than formalize this, I’ll illustrate it with an example and leave the formalization to you. Note that $(0)$ implies that $$\sum_{d\mid n}a_d=2^n\;,$$ where as usual the sum is taken over positive divisors. Consider $n=60=2^2\cdot3\cdot5$:
$$a_{60}=2^{60}-(a_1+a_2+a_3+a_4+a_5+a_6+a_{10}+a_{12}+a_{15}+a_{20}+a_{30})\;.$$
The maximal proper divisors of $60$ are $30,20$, and $12$, so every divisor of $60$ is a divisor of one of these three numbers, and to a first approximation $a_{60}$ is $2^{60}-2^{30}-2^{20}-2^{12}$. However, if $d$ is a common divisor of $30$ and $20$, say, then $a_d$ has been subtracted twice from $2^{60}$, once in $2^{30}$ and once in $2^{20}$, so it must be added back in. In particular, that’s true for every divisor of $\gcd(30,20)=10$, so we must add back in $\sum_{d\mid 10}a_d=2^{10}$. The same goes for divisors of $\gcd(30,12)=6$ and of $\gcd(20,12)=4$, so a better approximation to $a_{60}$ is $$2^{60}-2^{30}-2^{20}-2^{12}+2^{10}+2^6+2^4\;.$$ However, if $d\mid\gcd(30,20,12)=2$, then $a_d$ has now been subtracted three times and added back in $3$ times, so we must subtract $2^2$ for the correct result:
$$a_{60}=2^{60}-2^{30}-2^{20}-2^{12}+2^{10}+2^6+2^4-2^2\;.$$
A little thought shows that $(2)$ always yields the same result as the inclusion-exclusion argument.
Someone has kindly sent me a translation to Portuguese:
Seja $a_n$ o número de sequências aperiódicas de comprimento $n$. Repare que $a_1=2$, pois as sequências $0$ e $1$ são trivialmente aperiódicas. Suponha que $\sigma$ é uma sequência periódica de comprimento $n$, de período mínimo $d$. Seja $\beta$ o bloco periódico de comprimento $d$; então $\beta$ é uma sequência aperiódica de comprimento $d$. Reciprocamente, se $0<d<n$ e $d\mid n$, então para cada sequência aperiódica de comprimento $d$ a sequência $$\underbrace{\beta\beta\ldots\beta}_{n/d\text{ vezes}}$$ é uma sequência periódica de comprimento $n$ e período mínimo $d$. Segue-se que há$$\sum\{a_d:0<d<n\text{ e }d\mid n\}$$ sequências periódicas de comprimento $n$ e portanto que
$$a_n=2^n-\sum\{a_d:0<d<n\text{ e }d\mid n\}\;.\tag{0}$$ Seja $p$ um primo. Então $$a_{p^n}=2^{p^n}-\sum_{k=0}^{n-1}a_{p^k}\;,\tag{1}$$ e calcular alguns valores é muito instrutivo: $$\begin{array}{cc}0&1&2&3\\2&2^p-2&2^{p^2}-2^p&2^{p^3}-2^{p^2}\end{array}$$ Isto leva a conjeturar que $$a_{p^n}=2^{p^n}-2^{p^{n-1}}$$ para $n>0$, e a conjetura é facilmente demonstrável por indução usando $(1)$. Mais geralmente, suponha que $n=p_1^{r_1}\ldots p_m^{r_m}$, onde $p_1,\ldots,p_m$ são primos distintos e $r_1,\ldots,r_m\ge 1$. Construa o produto $$\prod_{k=1}^mp_k^{r_k-1}(p_k-1)=\left(\prod_{k=1}^mp_k^{r_k-1}\right)\prod_{k=1}^m(p_k-1)=\left(\prod_{k=1}^mp_k^{r_k-1}\right)\sum_{S\subseteq[m]}(-1)^{m-|S|}\prod_{k\in S}p_k\;.$$ Para cada $S\subseteq[m]$ seja $$\alpha_S=\left(\prod_{k=1}^mp_k^{r_k-1}\right)\prod_{k\in S}p_k\;;$$ então $$a_n=\sum_{S\subseteq[m]}(-1)^{m-|S|}2^{\alpha_S}\;.\tag{2}$$ Por exemplo, se $p$ e $q$ são primos distintos, $$a_{p^2q^2}=2^{\alpha_{\{p,q\}}}-2^{\alpha_{\{p\}}}-2^{\alpha_{\{q\}}}+2^{\alpha_\varnothing}=2^{p^2q^2}-2^{p^2q}-2^{pq^2}+2^{pq}\;.$$ Você provavelmente consegue provar isto por indução usando $(0)$, mas é mais fácil ver que é verdade por um raciocínio de inclusão-exclusão. Em vez de formalizar isto, irei ilustrar com um exemplo e deixar a formalização para você. Repare que $(0)$ implica que $$\sum_{d\mid n}a_d=2^n\;,$$ onde, como habitual, a soma é tomada sobre os divisores positivos. Considere $n=60=2^2\cdot3\cdot5$: $$a_{60}=2^{60}-(a_1+a_2+a_3+a_4+a_5+a_6+a_{10}+a_{12}+a_{15}+a_{20}+a_{30})\;.$$ Os divisores próprios maximais de $60$ são $30,20$ e $12$, portanto qualquer divisor de $60$ é um divisor de um destes três números e, como primeira aproximação $a_{60}$ é $2^{60}-2^{30}-2^{20}-2^{12}$. Contudo, se $d$ é um divisor comum a $30$ e $20$, por exemplo, então $a_d$ foi subtraída duas vezes de $2^{60}$, uma em $2^{30}$ e outra em $2^{20}$, por isso tem que se adicionar de volta. Em particular, isso é verdade para qualquer divisor de $\gcd(30,20)=10$, por isso devemos somar de volta $\sum_{d\mid 10}a_d=2^{10}$. O mesmo vale para os divisores de $\gcd(30,12)=6$ e de $\gcd(20,12)=4$, por isso uma melhor aproximação a $a_{60}$ é $$2^{60}-2^{30}-2^{20}-2^{12}+2^{10}+2^6+2^4\;.$$ No entanto, se $d\mid\gcd(30,20,12)=2$, então $a_d$ foi subtraída três vezes e adicionada de volta três vezes, por isso temos que subtrair $2^2$ para obter o resultado correcto: $$a_{60}=2^{60}-2^{30}-2^{20}-2^{12}+2^{10}+2^6+2^4-2^2\;.$$ Uma ligeira reflexão permite concluir que $(2)$ fornece sempre o mesmo resultado que o argumento de inclusão-exclusão.