Conjectura de Collatz

Uma excelente forma de aprender, é tentar resolver problemas. A gente ja comentou aqui sobre o project Rosalind e o project Euler. Eles tem excelentes problemas, que são bem instrutivos tentar resolver. Agora eu descobri outro lugar, que funciona de forma similar, mas tem problemas de computação, o UVa Online Judge. E aqui vamos para o primeiro problema, para ver como funciona.

A conjectura de Collatz, também conhecida como problema 3n + 1 é uma sequência de números, como a sequência de fibonacci. É uma função que qualquer número que a gente coloca nela termina em 1.

A função é essa:

   f(n) = \left\{       \begin{array}{lr}         n/2 & : se\ {n \equiv 0} (mod\ 2)\\         3n+1 & : se\ {n \equiv 1} (mod\ 2)       \end{array}     \right.

Bem, as vezes é mais fácil olhar a função na linguagem do R, as vezes fica mais fácil entender o que fazer. No R essa função fica assim:

collatz<-function(n) {
    if( (n %% 2) == 0 ) {
        n<-n/2
    } else {
        n<-n*3+1
    }
    return(n)
}

Agora se a gente digitar collatz(n), onde n é um número qualquer e temos o próximo valor da sequência.

> collatz(22) [1] 11

Certo, para ver a sequência inteira, basta fazermos isso até chegar a 1.
Podemos fazer uma segunda função, que usa essa primeira para cumprir essa tarefa no R

seqcollatz<-function(n) {
    vetor<-c(n)
    i<-1
 
    while(vetor[i]!=1) {
        vetor[i+1]<-collatz(vetor[i])
        i<-i+1
    }
 
    return(vetor)
}

E voala, podemos ver a sequência e o seu tamanho.

> seqcollatz(22) [1] 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 > seqcollatz(10) [1] 10 5 16 8 4 2 1

Uma característica legal, é que se você for olhar a sequência inteira, como tudo converge para o 1, se a gente olhar do 1 para frente, podemos pensar nas possibilidades de inicio na forma de um grafo.

exemplo

Veja que de qualquer número que começamos, cedo ou tarde, a gente entra num “trilho” rumo ao número 1. Alias, todo mundo converge para o 8, mas o tamanho da sequência não é obvia, veja como o 9 gera uma sequência enorme, enquanto o 16 por exemplo, gera uma sequência curta.

Mas o problema é mais simples que entender a estrutura dessa sequência, ele simplesmente quer dar 2 entradas, dois números inteiros, e devemos ver o tamanho da sequência a todos os números dentro desse intervalo de dois inteiros e dizer qual foi a maior.

Então a entrada é um conjunto de pares de números, algo como:

1 10 100 200 201 210 900 1000

E a saída esperada para essa entrada é:

1 10 20 100 200 125 201 210 89 900 1000 174

Ou seja entre 1 e 10, a maior sequência tem 20 elementos, que é a serie formada quando começamos no 9.

> seqcollatz(9) [1] 9 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 > length(seqcollatz(9)) [1] 20

Como UVa Online Judge não aceita programas em R, então temos que fazer usando alguma das linguagens que ele aceita. Em C, minha tentativa ficou assim.

#include <stdio.h>
 
/* Função que calcula o proximo valor na sequencia de collatz*/
int collatz(int n) {
  if(n!=1) {
    if(n%2==0) {
      n=n/2;
    } else {
      n=n*3+1;
    }
  }
    return n;
}
 
/* Função que calcula o tamanho da sequencia para um determinado n*/
int seqcollatz(int n) {
  int ciclo=1;
  while(n!=1) {
      n=collatz(n);
      ciclo++;
  }
  return ciclo;
}
 
int main(void){
  int a,b,i,ciclo,maior,x,y;
 
  while (scanf("%d %d", &x, &y) != EOF) {
 
    if(x>y) {
      a=y;
      b=x;
    } else {
      a=x;
      b=y;
    }
 
    maior=1;
 
    for(i=a;i<=b;i++) {
      ciclo=seqcollatz(i);
      if(maior<ciclo) {
	maior=ciclo;
      }
    }
 
    printf("%d %d %d\n",x,y,maior);
  }
  return 0;
}

Então são duas funções auxiliares, como a gente estava olhando em R, uma da o próximo número na sequência, e a outra verifica o tamanho da sequência.

Alguma coisa especiais são necessárias, como a entrada não tem um número de casos a serem testados, a gente precisa de algo especial no scanf, para ele parar quando não houver mais entradas. o != EOF, não sei o que isso faz perfeitamente para falar a verdade, mas funciona.

Além disso o problema tem umas pegadinhas.
Primeiro em nenhum momento ele diz que as entradas vão estar na ordem, menor depois maior, então isso precisa ser testado, e eles tem que ser impressos no final na ordem que entraram. Eu apanhei um bocado para entender isso.

Submetendo esse programa, eu tive uma resposta correta, mas uma bosta, fiquei em 22948 no ranking. Mas eficiência fica para a próxima. O legal que é possível submeter programa em java também.

Meu programa em java ficou assim:

import java.util.Scanner;
 
class main {
 
	public static int collatz(int n){
		 if(n!=1) {
			    if(n%2==0) {
			      n=n/2;
			    } else {
			      n=n*3+1;
			    }
			  }
			    return n;
	}
 
	public static int seqcollatz(int n){
		int ciclo=1;
 
		  while(n!=1) {
 
		      n=collatz(n);
		      ciclo++;
 
		  }
 
		  return ciclo;
	}
 
	public static void main(String[] args) {
 
		int a,b,i,ciclo,maior,x,y;
 
		Scanner leitor = new Scanner(System.in);
 
		while(leitor.hasNext()) {
			x=leitor.nextInt();
			y=leitor.nextInt();
 
			   if(x>y) {
				      a=y;
				      b=x;
				    } else {
				      a=x;
				      b=y;
				    }
 
				    maior=1;
 
				    for(i=a;i<=b;i++) {
 
				      ciclo=seqcollatz(i);
 
				      if(maior<ciclo) {
					maior=ciclo;
				      }
 
				    }
 
				    System.out.printf("%d %d %d\n",x ,y ,maior);
 
		}
 
		leitor.close();
 
	}
 
}

A ideia é exatamente a mesma do programa em C.

Ele funcionou beleza no terminal, mas não sei porque o UVa Online Judge não aceita ele, fica dando um runtime error, mas no terminal tudo da certo:

$ javac collatzsequence.java $ java collatzsequence < input.txt 1 10 20 100 200 125 201 210 89 900 1000 174

Agora é começar a tentar resolver mais problemas, mas essa é mais uma opção além do Rosalind e do Project Euler para aprender mais um pouquinho de programação.

Os scripts e programas vão ficar disponíveis la no repositório recologia do github, se alguém quiser olhar, porque as vezes alguns problemas são frustantes, principalmente quando ficamos cometendo erros bobos. Se alguém souber como resolver direito o programa em Java, e melhorar a performance em C eu agradeço muito sugestões. Em C imagino que operações em Bits sejam mais rápidas.