Korean, Edit

Collatz Conjecture in C Language

Higher category : 【C Language】 C Language Table of Contents

a. GitHub

The Collatz conjecture, named after Lothar Collatz, who first proposed this conjecture in 1937, is also known as the 3n+1 problem or the hailstone sequence problem. The Collatz conjecture states that for any natural number, the following algorithm will always terminate:

1. Take input n.

2. If n is 1, stop.

3. If n is an odd number, compute 3n + 1.

4. If n is an even number, divide it by 2.

5. Repeat steps 2-4.

If we take n = 22 as an example, the algorithm will produce the following sequence of values:

22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

While this algorithm terminates for most numbers within the range we typically deal with (up to 20 × 258), it has not been proven to terminate for all possible inputs. Some question whether it might be an unsolvable problem. The following algorithm contains an approach to find the number with the longest cycle length among natural numbers a and b (up to approximately 10,000,000). Optimization of this algorithm is left for individual consideration. Furthermore, by applying the C2 algorithm, you can output the cycle for a specific number.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define count_set 200000000
/* 
	This code shows you the least length of n's array between a and b defined by Collatz's problem.
	Assumption: all counts are below maximum value of 'short' data type.
	Procedure goes as;
		1 (over)
		2 → 1 (over)
		3 → 10 → 5 → 16 → 8 → 4 → 2 (over)
		4 (over)
		5 (over)
		6 → 3 (over)
		7 → 22 → 11 → 34 → 17 → 52 → 26 → 13 → 40 → 20 → 10 (over) 
*/

short set[count_set + 1] = {0, };
int count;
void C2(long long int n){
	count ++;
	if(n == 1);
	else if(n % 2 == 0) C2(n / 2);
	else C2(3 * n + 1);
}

int C(long long int n){
	if(n > count_set){
	// "n > count_set" means too big number just has appeared.
		count = 0;
		C2(n);
		return count;
	}
	if(set[n] != 0) return set[n];

	// if set[n] = 0, set[n] should be filled the proper number.
	if(n % 2 == 1) set[n] = C(3 * n + 1) + 1; // n is odd
	else set[n] = C(n / 2) + 1; // n is even
	return set[n];
}

int main(int argc, char *argv[]) {
	long long int i, a, b

, max_order = 1, max = 1;
	scanf("%lld %lld", &a, &b);
	set[1] = 1;
	for(i = a; i <= b; i ++){
		set[i] = C(i);
		if(set[i] > max){
			max_order = i;
			max = set[i];
		}
	}
	printf("%lld %lld", max_order, max);
	return 0;
}

Input: 2016.03.01 11:34