14問目

正の整数の数列が以下の反復規則で定められている.
.
上記のルールを使って13から始めると, 次の数列が得られる.
.
この数列には(13から1まで)10個の数字が含まれている. これはまだ未解決問題(Collatz 問題)なのだが, どの数字から始めても1に辿り着くと考えられている.
1000000 未満のどの数字で始めた場合に, 数列が一番長くなるか?

http://projecteuler.net/index.php?section=problems&id=14

題材が有名な未解決問題だということで, 非常にやる気が上がりました. (変な云い方だが, 私はこういう問題に萌えます.)

しっかしこの問題も糸口ってどこにあるんでしょうね.
まず第一感として, 「保存量を見付ける」か「1回の反復で1だけ減る指標を見付ける」という方針が思い付くのですが, 反復ルールが mod しか使ってない上に, 半分にしたり3倍して1を足したりされてしまうと, 保存する量というのはなかなか考え付かないですね. 2つ目の方針も行き当たりばったりでは見付からなさそうだし. さすが未解決問題!

さてプログラムの方ですが, 如何に計算量を節約できるかをテーマに組んでみました.
問題文の例で云うと, 13から始めたときの数列の長さを調べたら, 同時に1, 2, 4, 5, 8, 10, 16, 20, 40から始めたときの数列の長さも分かっています. なので二度手間を省くため, 上の反復規則を逆にして,

1から始めて長さを計算しています.
かと云ってこれで全てを計算すると関数呼び出しが多くなってしまうのでほどほどで止めて, 計算し切っていない部分は最後に個々に計算してあります. gdb 使ってバグを修正しつつ進め, 無事クリア.

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define MAX_NUMBER 1000000
#define MAGNIF 30

int numbers[MAGNIF * MAX_NUMBER];

int solveVer00();
int solveVer01();
void initArray();
void CollatzCountUp(int, int);
long long CollatzCountDown(long long);

int main() {
	fprintf(stdout, "Solution: %d\n", solveVer01());

	return EXIT_SUCCESS;
}

int solveVer00() {
	int i;
	int maxCount;
	int maxNum;
	int count;

	numbers[1] = 1;
	for (i = 1, maxCount = 0; i < MAX_NUMBER; i++) {
		count = CollatzCountDown(i);
		if (count > maxCount) {
			maxCount = count;
			maxNum = i;
		}
	}

	return maxNum;
}

int solveVer01() {
	int i;
	int max;
	int maxNum;

	initArray();
	CollatzCountUp(1, 1);

	for (i = 1, max = 0; i < MAX_NUMBER; i++) {
		if (numbers[i] == 0) {
			numbers[i] = CollatzCountDown(i);
		}
		if (numbers[i] > max) {
			max = numbers[i];
			maxNum = i;
		}
	}

	return maxNum;
}

void initArray() {
	int i;
	for (i = 0; i < MAGNIF * MAX_NUMBER; i++) {
		numbers[i] = 0;
	}
}

void CollatzCountUp(int number, int count) {
	numbers[number] = count;
	if ((number % 6) == 4
		&& numbers[(number-1)/3] == 0) {
		CollatzCountUp((number - 1) / 3, count + 1);
	}

	if (number > MAGNIF * MAX_NUMBER / 2) {
		return;
	} else {
		CollatzCountUp(number * 2, count + 1);
	}
}

long long CollatzCountDown(long long number) {
	if (number < MAGNIF * MAX_NUMBER
		&& numbers[number] > 0) {
		return numbers[number];
	} else if ((number % 2) == 0) {
		return CollatzCountDown(number / 2) + 1;
	} else {
		return CollatzCountDown(3 * number + 1) + 1;
	}
}