Esse é um dos problemas mais simples que tem no UVa mas ao mesmo tempo é muito interessante. O problema 3n + 1, também chamado de Conjectura de Collatz, é um problema da matemática que nunca foi resolvido.

Basicamente é o seguinte:

• Se o número é par, então divida por dois.
• Se o número é ímpar, então multiplique por três e some por um.
• 

Agora que temos a função definida, vamos realizar essa operação repetidamente, começando com um inteiro positivo e depois usando o resultado em cada passo:

O interessante é que essa seqüência parece sempre resultar em .

Programando

O desafio enunciado no UVa Online Judge pede para se contar o maior número de m-cíclos em um determinado intervalo de inteiros n, m.

Como eu gosto de coisas simples, fiz um algoritmo em C bem simples. Não recomendo algoritmo complexos.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

#include <stdio.h>
 
int collatz(int n) {
	int i = 1;
	while(n > 1) {
		if((n % 2) != 0)
			n = (3*n) + 1;
		else
			n = n/2;
		++i;
	}
	return i;
}
 
int main (int argc, char const *argv[])
{
	int i, j;
	while(scanf("%d %d", &i, &j) == 2) {
		int i2, j2, k;
		int max = 0;
 
		if (j < i) {
			i2 = j;
			j2 = i;
		} else {
			i2 = i;
			j2 = j;
		}
 
		for (k = i2; k <= j2; ++k) {
			int atual = collatz(k);
			if (max < atual) {
				max = atual;
			}
		}
 
		printf("%d %d %d\n", i, j, max);
	}
	return 0;
}

ou pelo pastebin

Testando as seguintes entradas
1 10
100 200
201 210
900 1000
1 999999
1000 900

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

Parece tudo certo!

Agora fica de exercício descobrir a complexidade desse algoritmo.