Bem-vindo ao Umamão!

Question

2

Numa dízima periódica, o tamanho do período é definido como o número de algarismos que se repetem indefinidamente, na mesma ordem. Assim, por exemplo, temos que:

$$\frac{1}{7} = 0,142857142857142857... = 0,(142857)$$

Sendo então que $\frac{1}{7}$ tem tamanho de período 6.

Outro exemplo:

$$\frac{1}{6} = 0,166666666666666666... = 0,1(6)$$

Sendo então que $\frac{1}{6}$ tem tamanho de período 1.

Primeiro, é fácil ver que toda dízima da forma $\frac{a}{n}$ tem tamanho máximo $(n-1)$. Daí, segundo a Wikipedia, a função de Carmichael $\lambda(n)$ define um patamar superior para o tamanho do período de $\frac{1}{n}$ (na verdade, a afirmação é mais forte: ela diz que o tamanho do período é um divisor de $\lambda(n)$).

Então, vem a pergunta: é possível, de forma determinística (i.e., algorítmica), determinar o tamanho exato (e não apenas limites superiores) do período de uma fração $\frac{1}{n}$? Como?

edited Jul 25 at 20:38

Helder Ribeiro♦♦
1,648●3●10

asked Jul 25 at 16:07

aires
642●9

Helder Ribeiro · Accepted Answer · 2010-07-25 20:37:45Z UTC

3

É fácil fazer isso em $O(n)$.

É só simular a divisão longa e ao mesmo tempo construir um vetor de sucessores indexado pelos restos possíveis, ou seja, com indices $[0,n)$. O algoritmo para na primeira vez que aparecer um valor já marcado no vetor.

Daí é só procurar um ciclo no vetor (que é um jeito compacto de representar o grafo dos restos), repare que por construção só vai haver um único ciclo no grafo. Por isso, uma busca em profundidade basta para encontrar o tamanho deste ciclo.

A questão mais difícil é se é possível fazer isso em tempo $O(\lg n)$. Eu acho que não, a menos que faça parte da entrada a fatoração (em primos) de $n$. Porque eu acho que outros métodos baseados em teoria dos números devem usar a fatoração de $n$. O próprio cálculo de $\lambda(n)$ se baseia na fatoração de $n$ .

edited Jul 25 at 20:37

Helder Ribeiro♦♦

answered Jul 25 at 17:56

sacomoto♦♦
764●6

O "vetor de sucessores" que você diz é um vetor que vai guardando um valor autoincrementante na posição dos restos que vão saindo? Quer dizer, no caso do 1/7 seria [nil, 5, 1, 0, 3, 4, 2]? Se você para quando acha alguém marcado (i.e., quando acha um ciclo), não é só pegar nesse momento o valor do autoincrementante (+1, se começou do zero) e você tem o tamanho do período? Por que precisa da busca em profundidade? – Helder Ribeiro♦ Jul 25 at 22:28

1

Repare que se o algoritmo fosse da maneira que você propõe ele estaria errado. O vetor de sucessores é INDEXADO por $[0,n)$, ou seja, cada posição do vetor representa um dos restos possíveis. A divisão longa gera uma sequência de restos, se em uma dada iteração $i$ o resto gerado é $a_i$, então fazemos vetor[$a_{i-a}$] = $a_i$. – sacomoto♦ Jul 25 at 22:41

Ops, tem um typo no meu último comentário. O certo é vetor[$a_{i-1}$] = $a_{i}$ – sacomoto♦ Jul 25 at 23:09

1

Sim, o meu vetor também é indexado por $[0,n)$. Se em uma dada iteração $i$ o resto gerado é $a_i$, eu faço vetor[$a_i$] = i++, mas antes verifico: if vetor[$a_i$] != nil; break, e o resultado do tamanho é $i$. – Helder Ribeiro♦ Jul 26 at 1:58

1

Na verdade o que você armazena no vetor é irrelevante, ele só precisa ter algum marcador indicando se a posição já foi usada ou não. Eu poderia só inicializar tudo com 0 e colocar 1 quando eu já passei por lá, mantendo a contagem de $i$ fora do vetor. Aí quando eu chegasse em um 1 eu simplesmente imprimia a contagem. – Helder Ribeiro♦ Jul 26 at 2:00

show 2 more comments

Como determinar o tamanho do período de uma dízima periódica da forma 1/n?

1 Answer