Reuniões de domingo e 3x+1

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxxxxxxx>]

Hoje o palestrante serei eu. Domingo que vem (23/5) não haverá reunião.
No outro domingo (30/5) o palestrante será o Pablo Emanuel, estudante
na PUC e no IMPA e ganhador de várias medalhas em várias olimpíadas de
matemática.

Apresentarei hoje a solução de alguns dos problemas propostos na minha
primeira "aula" e alguns problemas/resultados novos de contagem.

Alguém recentemente perguntou sobre o problema 3x+1 e eu fiz a observação
que ele está em aberto e que os matemáticos têm poucas esperanças de
resolver este problema em breve.

Recapitulando, definimos f como
f(n) = 3n+1 se n é ímpar, f(n) = n/2 se n é par.
Como sempre, definimos f^k(n) = f(f(...f(n)...)) com k f's,
ou seja, f^0(n) = n, f^(k+1)(n) = f(f^k(n)).
Para um dado n, consideramos a seqüência f^k(n).
Assim, por exemplo, para n = 41 obtemos a seqüência:
 
41,124,62,31,94,47,142,71,214,107,322,161,484,242,121,364,182,91,274,137,
412,206,103,310,155,466,233,700,350,175,526,263,790,395,1186,593,1780,890,
445,1336,668,334,167,502,251,754,377,1132,566,283,850,425,1276,638,319,958,
479,1438,719,2158,1079,3238,1619,4858,2429,7288,3644,1822,911,2734,1367,
4102,2051,6154,3077,9232,4616,2308,1154,577,1732,866,433,1300,650,325,976,
488,244,122,61,184,92,46,23,70,35,106,53,160,80,40,20,10,5,16,8,4,2,1,4,2,1,...

O problema é decidir se para qualquer inteiro n a seqüência acaba
chegando a 4,2,1,4,2,1,4,2,1,...

Escrevi um pequeno programa em C que calculou a lista de inteiros acima:

#include <stdlib.h>
#include <stdio.h>
#include <gmp.h>
int main(int argc, char *argv[])
{
  mpz_t n0, aux;
  mpz_init(n0); mpz_init(aux);
  mpz_set_str(n0,argv[1],10); mpz_out_str(stdout,10,n0);
  while ( mpz_cmp_ui(n0,1) > 0 )
  {
    fprintf(stdout,","); mpz_fdiv_r_2exp(aux,n0,(long)(1));
    if ( mpz_cmp_ui(aux,0) == 0 ) 
    { mpz_fdiv_q_2exp(n0,n0,(long)(1)); }
    else
    { mpz_mul_ui(n0,n0,(long)(3)); mpz_add_ui(n0,n0,(long)(1)); }
    mpz_out_str(stdout,10,n0);
  }   
  return(0);
}

Este programa usa a biblioteca gmp e portanto pode trabalhar com inteiros
arbitrariamente grandes. A biblioteca gmp pode ser obtida
(gratuita e legalmente) em ftp://ftp.gnu.org/gnu/gmp/gmp-2.0.2.tar.gz
(e vem com ampla documentação). Outra biblioteca semelhante é giantint
que pode ser obtida (também gratuita e legalmente) em http://www.perfsci.com/.
Nos dois casos você terá as fontes (e não binários)
de modo que estas bibliotecas funcionam em qualquer sistema operacional.

Por outro lado, o Gugu me indicou algumas referências interessantes
sobre este problema e eu encontrei algumas outras. O artigo
http://www.cecm.sfu.ca/organics/papers/lagarias/paper/html/paper.html
apresenta uma história do problema, de resultados parciais e de tentativas
de resolução. O endereço
http://ug.cs.dal.ca/~campbell/colllink.html
tem uma lista de vários links interessantes.

[]s, N.

http://www.mat.puc-rio.br/~nicolau