Questão 10: Na sequência de Collatz, se n é par, n=n / 2; se n é ímpar, n=3 n+ 1. Crie uma função contar_passos_collatz (n) que retorne quantos “passos”(iterações do while) são necessários para n chegar até 1 .
Exemplo: contar_passos_collatz (6) \rightarrow(6,3,10,5,16,8,4,2,1) deve retornar 8.

Passo 1

O enunciado pede para criar uma função chamada contar_passos_collatz que, dada uma entrada inteira positiva n, aplique a regra da sequência de Collatz repetidamente até que n chegue a 1, e retorne quantos “passos” (iterações do laço while) foram necessários. As regras são:
  • se n é par, substituir n por \dfrac{n}{2};
  • se n é ímpar, substituir n por 3n+1.
O enunciado dá um exemplo explícito: para n=6 a sequência é
6,\,3,\,10,\,5,\,16,\,8,\,4,\,2,\,1
e a função deve retornar 8 (porque foram 8 iterações até alcançar 1).
Informações relevantes dadas:
  • entrada: um inteiro n (assumiremos n\ge 1);
  • saída: um inteiro que é o número de iterações necessárias para n chegar a 1;
  • as operações envolvidas são divisão inteira por 2 quando n é par, e multiplicação por 3 mais 1 quando n é ímpar;
  • a contagem deve considerar cada aplicação da regra como um passo (cada iteração do while).

Passo 2

Definição clara do que vamos implementar (sem ainda programar): queremos um procedimento iterativo que:
  1. receba um inteiro n;
  2. repita enquanto n\neq 1:
    • testar paridade de n;
    • atualizar n conforme a regra de Collatz;
    • incrementar um contador de passos;
  3. ao sair do laço, retornar o contador.
Observações importantes e suposições:
  • se n=1, não precisamos fazer nenhuma iteração e o resultado deve ser 0;
  • assumimos n inteiro positivo; se recebermos outro tipo de entrada, é razoável sinalizar erro (vamos tratar isso na implementação final);
  • a conjectura de Collatz afirma que toda n positiva alcança 1, e aqui o enunciado assume que a sequência de fato chega a 1 (ou seja, podemos usar while n != 1 sem nos preocupar com um laço infinito para os casos do enunciado).

Passo 3

Vamos explicar cada parte do algoritmo com calma (aquelas coisas que costumam aparecer na prova).
  1. Contador de passos: precisamos de uma variável inteira passos inicializada em 0. Essa variável contabiliza quantas vezes aplicamos a regra até chegar em 1.
  2. Teste de paridade: para decidir se n é par ou ímpar usamos o resto da divisão por 2, ou seja, o operador \bmod.
  • n é par se n \bmod 2 = 0.
  • n é ímpar se n \bmod 2 = 1.
Exemplos rápidos: 6 \bmod 2 = 0 (par); 7 \bmod 2 = 1 (ímpar).
  1. Atualização de n:
  • se n é par, fazemos n \leftarrow \dfrac{n}{2}. Na maioria das linguagens de programação precisamos garantir divisão inteira; em Python usamos n //= 2 para manter n inteiro;
  • se n é ímpar, fazemos n \leftarrow 3n + 1.
  1. Estrutura de repetição: enquanto n \neq 1 repetimos os passos 2–3. Cada vez que entramos no corpo do laço incrementamos passos em 1.
  2. Caso base: se a entrada já for n=1, o while não é executado e retornamos 0.

Passo 4

Vamos ver o pseudocódigo e explicar linha a linha (é assim que eu faria numa prova se pedissem o algoritmo):
Pseudocódigo:
  • receber n
  • se n < 1 então sinalizar erro (entrada inválida)
  • passos \leftarrow 0
  • enquanto n \neq 1 faça:
    • se n \bmod 2 = 0 então n \leftarrow \dfrac{n}{2}
    • senão n \leftarrow 3n + 1
    • passos \leftarrow passos + 1
  • retornar passos
Explicação de cada linha:
  • "receber n" indica que a função aceita um argumento inteiro;
  • checagem n<1: protege contra entradas inválidas (zero ou negativas);
  • inicialização passos=0: conta a quantidade de iterações;
  • condição do while n\neq 1: mantemos o laço enquanto não atingimos o objetivo;
  • dentro do while aplicamos a regra adequada (par/ímpar) e aumentamos o contador;
  • ao terminar, retornamos o total acumulado em passos.

Passo 5

Traço detalhado do exemplo n=6 (esse traço é o que facilita muito aprender pela prática — faça parecido na prova!):
Inicialmente n=6, passos=0.
Iteração 1:
  • 6 \bmod 2 = 0 (par), então n \leftarrow 6/2 = 3.
  • passos \leftarrow 1.
    Sequência até aqui: 6 \to 3.
Iteração 2:
  • 3 \bmod 2 = 1 (ímpar), então n \leftarrow 3\cdot 3 + 1 = 10.
  • passos \leftarrow 2.
    Sequência: 6 \to 3 \to 10.
Iteração 3:
  • 10 é par, n \leftarrow 10/2 = 5.
  • passos \leftarrow 3.
    Sequência: 6 \to 3 \to 10 \to 5.
Iteração 4:
  • 5 é ímpar, n \leftarrow 3\cdot 5 + 1 = 16.
  • passos \leftarrow 4.
    Sequência: 6 \to 3 \to 10 \to 5 \to 16.
Iteração 5:
  • 16 é par, n \leftarrow 16/2 = 8.
  • passos \leftarrow 5.
    Sequência: 6 \to 3 \to 10 \to 5 \to 16 \to 8.
Iteração 6:
  • 8 é par, n \leftarrow 8/2 = 4.
  • passos \leftarrow 6.
    Sequência: 6 \to 3 \to 10 \to 5 \to 16 \to 8 \to 4.
Iteração 7:
  • 4 é par, n \leftarrow 4/2 = 2.
  • passos \leftarrow 7.
    Sequência: 6 \to 3 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2.
Iteração 8:
  • 2 é par, n \leftarrow 2/2 = 1.
  • passos \leftarrow 8.
    Sequência final: 6 \to 3 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 1.
Agora n=1, saímos do while e retornamos passos = 8, que é exatamente o resultado esperado no exemplo.

Passo 6

Dicas práticas e observações (úteis para a prova e para implementar sem erro):
  • Use divisão inteira ao dividir por 2 para manter n como inteiro (em Python use //).
  • Proteja a função contra entradas inválidas (por exemplo, n <= 0) e explique na resposta que o domínio é n\in\{1,2,3,\dots\}.
  • Em Python não precisamos nos preocupar com overflow de inteiros (eles têm precisão arbitrária), então valores grandes de n não causarão erro de overflow, apenas podem necessitar de muitas iterações.
  • A conjectura de Collatz ainda não foi provada globalmente, mas para o contexto do exercício assumimos que a sequência chega a 1 em tempo finito para as entradas de interesse.

Passo 7

Preparação final para implementar em código: a versão que vou retornar é direta, clara e segue o pseudocódigo explicado. Ela:
  • verifica se n é inteiro positivo;
  • inicializa o contador;
  • executa o while n != 1 aplicando as regras de par/ímpar;
  • incrementa o contador a cada iteração;
  • retorna o contador.
Agora eu disponibilizo a implementação final em Python abaixo na seção de resposta.

Resposta

def contar_passos_collatz(n):
“”"
Retorna o número de iterações necessárias para que n alcance 1
pela regra de Collatz:
- se n é par: n = n // 2
- se n é ímpar: n = 3*n + 1
Entrada: n (inteiro, n >= 1)
Saída: número inteiro de passos
“”"
if not isinstance(n, int) or n < 1:
raise ValueError(“n deve ser um inteiro positivo (n >= 1)”)
passos = 0
while n != 1:
if n % 2 == 0:
n //= 2
else:
n = 3 * n + 1
passos += 1
return passos

Exercícios relacionados