Wu Yudong's Blog

The following iterative sequence is defined for the set of positive integers:

n  -> n/2 (n is even)
n  -> 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

13 -> 4 -> 20 -> 10 -> 5 -> 168 -> 4 -> 2 -> 1

It can be seen that this sequenc -> e (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

题目大意：

以下迭代序列定义在整数集合上：

n  ->  n/2 (当n是偶数时) n  -> 3n + 1 (当n是奇数时)

应用以上规则，并且以数字13开始，我们得到以下序列：
13 -> 4 -> 20 -> 10 -> 5 -> 168 -> 4 -> 2 -> 1
可以看出这个以13开始以1结束的序列包含10个项。虽然还没有被证明（Collatz问题），但是人们认为在这个规则下，以任何数字开始都会以1结束。

以哪个不超过100万的数字开始，能给得到最长的序列？ 注意: 一旦序列开始之后，也就是从第二项开始，项是可以超过100万的。

方法1：

#include<stdio.h>
#include<math.h>
#include<stdbool.h>

int powcount(long long n)		//计算2的幂数
{
	int count = 0;
	while (n >>= 1)
		count++;
	return count;
}

bool ispower(long long v)		//判断n是否为2的幂
{
	if (((v & (v - 1)) == 0))
		return true;
	else
		return false;
}

int length(long long n)
{
	int sum = 1;
	while (1) {
		if (n == 1)
			break;
		if ((n & 1) == 0) {
			if (ispower(n))
				return sum + powcount(n);
			else
				n = n / 2;
		} else
			n = 3 * n + 1;
		sum++;
	}
	return sum;
}

int main()
{
	int i, t, k, max = 0;
	for (i = 2; i < 1000000; i++) {
		t = length(i);
		if (t > max) {
			max = t;
			k = i;
		}
	}
	printf("%lld\n", k);
	return 0;
}

方法2：

#include<stdio.h>
#include<math.h>
#include<stdbool.h>

int a[1000001];

void find()
{
	long long i, j, k, f, sum, max = 0;
	a[1] = 1, a[2] = 2;
	for (j = 3; j < 1000000; j++) {
		sum = 1, k = i = j;
		while (1) {
			if ((i & 1) == 0) {
				i = i / 2;
				if (i < k) {
					a[k] = sum + a[i];
					break;
				}
			} else {
				i = 3 * i + 1;
			}
			sum++;
		}
		if (a[k] > max) {
			max = a[k];
			f = k;
		}
	}
	printf("%d\n", f);
}

int main()
{
	find();
	return 0;
}

Answer:837799
Completed on Sun, 28 Jul 2013, 06:17