7 A conjetura de Collatz

7.1 A Conjetura de Collatz

$\newcommand{\N}{\mathbb N}$

Considere a seguinte função $f:\N\to \N$: \[ f(n)=\left\{\begin{array}{cc} n/2 & \mbox{se $n$ for par;}\\ 3n+1 & \mbox{se $n$ for ímpar.}\end{array}\right. \] A Conjetura de Collatz afirma que para todo $n\in\N$, existe um número $k$ tal que aplicando a função $f$ consecutivamente $k$ vezes em $n$, o resultado vai ser igual a $1$. Em outras palavras, para todo $n\in\mathbb N$, existe algum $k\geq 1$ tais que $f^k(n)=1$.

A conjetura foi atacada por vários matemáticos sem sucesso. Terence Tao recentemente conseguiu melhorar significativamente os reslutados existentes.

7.2 Tarefa 1

Escreva uma função collatz( n ) que toma $n$ como input e devolve $f(n)$. Faça testes da sua função com vários números.

A sua função deve comportar-se de acordo com os seguintes exemplos:

gap> collatz( 15 );
46
gap> collatz( 14 );
7
gap> collatz( 5 );
16

Pode ser que você já resolveu esta tarefa na Seção 5.7. Se não, precisa testar, usando if, (Seção 5.1) se o input é par ou ímpar e para isso pode usar a operação mod (Seção 2.1). Se precisar de ajuda com funções, consulte a Seção 5.6.

7.3 Tarefa 2

Escreva uma função nr_steps( n ) que vai calcular o número de vezes a função $f$ precisa ser aplicada em $n$ para obter o número $1$. Em outras palavras, nr_steps( n ) deve devolver o menor número $k$ tal que $f^k(n)=1$. Para $n=1$, nós vamos assumir que $f^0(1)=1$.

A sua função precisa devolver o resultado de acordo com os seguintes exemplos.

gap> nr_steps( 1 );
0
gap> nr_steps( 3 );
7
gap> nr_steps( 14 );
17
gap> nr_steps( 32 );
5

Você usará a função collatz( n ) na tarefa anterior em um laço while (Seção 5.3) ou repeat (Seção 5.4). Vai precisar também de variável local (explicado na Seção 5.6).

7.4 Tarefa 3

Escreva uma função max_nr_steps( n ) para determinar o número $k$ tal que nr_steps( k ) é maior possível para os números em $\{1,\ldots,n\}$. A função deve devolver uma lista (Seção 3.1) de comprimento $2$ tal que a primeira entrada da lista é o número $k$ e a segunda é o número nr_steps( k ).

O comportamento da sua função seguirá os seguintes exemplos:

gap> max_nr_steps( 1000 );
[ 871, 178 ]
gap> max_nr_steps( 10000 );
[ 6171, 261 ]
gap> max_nr_steps( 100000 );
[ 77031, 350 ]

Pode usar a função nr_steps( k ) escrita na tarefa anterior em um laço for (Seção 5.2) que roda na lista [1..n].

7.5 Tarefa 4

Vamos otimizar o código que foi escrito para a Tarefa 3. Calcular nr_steps( k ) separadamente para todo $k\in \{1,\ldots,n\}$ faz muita computação redundante. Por exemplo, calculando max_nr_steps( 6 ) deste jeito, fazemos as seguintes contas

1 → 1 
2 → 1
3 → 10 → 5 → 16 → 8 → 4 → 2 → 1 
4 → 2 → 1 
5 → 16 → 8 → 4 → 2 → 1
6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1

A computação nr_steps( 6 ) deve realizar que nr_steps( 3 ) já foi calculado e simplificar a conta por computar que nr_steps( 6 ) = nr_steps( 3 ) + 1. Escreva uma versão da função max_nr_steps_fast( n ) utilizando as computações anteriores e compare o tempo de execução das duas versões.

De acordo com o seguinte exemplo, calcular o valor maximal de nr_steps( k ) para k in [1..1000000] demora mais que $25$ segundos usando a função escrita para a Tarefa 3. A nova função faz esta computação em apenas $1,3$ segundos.

gap> max_nr_steps( 1000000 ); time;   
[ 837799, 524 ]
25391
gap> max_nr_steps_fast( 1000000 ); time;
[ 837799, 524 ]
1335

Denotando por $k_n$ o valor da função nr_steps( n ), guarde o valor de $k_n$ como o $k$-ésima entrada em uma lista. A lista pode ser uma lista esparsa (Seção 3.1). Provavelmente precisará das expressões break e continue (Seção 5.8). Pode usar também a variável interna time que devolve o tempo (em milisegundos) que a última instrução tomou (manual).