# Funções/Sequências (Functions/Sequence)

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.

• @Brian M. Scott Tank You for edited. – marcelolpjunior Nov 11 '13 at 17:07
• You’re welcome; Google translate did a pretty good job this time, so I just fixed a couple of little things. – Brian M. Scott Nov 11 '13 at 17:10
• @BrianM.Scott As for the question, can you help me? – marcelolpjunior Nov 11 '13 at 17:11
• I may be able to, but I need to think about it a little more to be sure. – Brian M. Scott Nov 11 '13 at 17:13
• @BrianM.Scott I need to understand how to do it, is for a challenge, I tried a bit of everything, but I know well these concepts of aperiodic sequences, among others. I would be eternally grateful if you can save me. – marcelolpjunior Nov 11 '13 at 17:15

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.

• Would you ask someone to translate to Portuguese? Using the google translator I still can not make a good read. Please. – marcelolpjunior Nov 20 '13 at 11:15

Maybe we can recapitulate the above in more compact form. Let $a_n$ be the number of aperiodic sequences. By definition we have that $$\sum_{d|n} a_d = 2^n.$$ By the Möbius Inversion Formula we thus have $$a_n = \sum_{d|n} 2^d \mu(n/d).$$ This gives for $n = p^k$ a power of a prime the result $$a_n = 2^{p^k}\mu(1) + 2^{p^{k-1}}\mu(p) = 2^{p^k}-2^{p^{k-1}}.$$ Here the MIF encapsulates inclusion-exclusion.

The sequence of the $a_n$ starts like this: $$2, 2, 6, 12, 30, 54, 126, 240, 504, 990, 2046, 4020, 8190, 16254, 32730,\ldots$$ which points us to OEIS A027375.

Portuguese version

Talvez seja possível recapitular a resposta acima de forma mais compacta. Seja $a_n$ o número de sequências aperiódicas. Por definição, $$\sum_{d|n} a_d = 2^n.$$ Pela fórmula de inversão de Möbius, então, $$a_n = \sum_{d|n} 2^d \mu(n/d).$$

Para $n=p^k$ uma potência de um primo, temos $$a_n = 2^{p^k}\mu(1) + 2^{p^{k-1}}\mu(p) = 2^{p^k}-2^{p^{k-1}}.$$

A inversão de Möbius, neste caso, expressa o princípio da inclusão-exclusão.

A sequência $(a_n)_n$ tem valores $$2, 2, 6, 12, 30, 54, 126, 240, 504, 990, 2046, 4020, 8190, 16254, 32730,\ldots$$ que apontam para a sequência OEIS A027375.

• I'm having trouble understanding what is this "argument of inclusion-exclusion" – marcelolpjunior Nov 20 '13 at 10:02
• Note that "above" and "below" varies here! If someone orders answers differently (like me), your question is actually the first to be read, so it is better just to give a concrete reference of what "above" is! =) – Pedro Tamaroff Nov 20 '13 at 15:19
• Marko, I edited your answer so I could add a Portuguese version, I hope you don't mind. – Ian Mateus Nov 22 '13 at 15:21
• @marcelolpjunior inclusion-exclusion principle is what you probably know as princípio da inclusão-exclusão. – Ian Mateus Nov 22 '13 at 15:23
• Nice: the MIF does make it very easy. – Brian M. Scott Nov 30 '13 at 17:34