[Project Euler #14][C++] 백만 이하로 시작하는 우박수 중 가장 긴 과정을 거치는 것은?

문제14 : 백만 이하로 시작하는 우박수 중 가장 긴 과정을 거치는 것은?

문제

양의 정수 n에 대하여, 다음과 같은 계산 과정을 반복하기로 합니다.

n → n / 2 (n이 짝수일 때)
n → 3n + 1 (n이 홀수일 때)

13에 대하여 위의 규칙을 적용해보면 아래처럼 10번의 과정을 통해 1이 됩니다.

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

아직 증명은 되지 않았지만, 이런 과정을 거치면 어떤 수로 시작해도 마지막에는 1로 끝나리라 생각됩니다.

(역주: 이것은 콜라츠 추측(Collatz Conjecture)이라고 하며, 이런 수들을 우박수(Hailstone Sequence)라 부르기도 합니다)

그러면, 백만(1,000,000) 이하의 수로 시작했을 때 1까지 도달하는데 가장 긴 과정을 거치는 수는 얼마입니까?

참고: 계산 과정에는 백만을 넘어가는 수가 나와도 괜찮습니다.

문제 해결 방법

• 하나하나씩 계산하는 방식(브루트 포스 방식)으로 문제를 해결하였다.
• long long 자료형으로 변수를 선언하지 않을 경우 113383에서 멈추므로 반드시 long long 자료형으로 변수를 선언해줘야 했다.
• 과정을 알아보기 위해 중간에 출력 함수 를 넣으면 결과값을 얻는데 오랜 시간이 걸린다.

소스 코드

	#include <iostream>
	using namespace std;
	#define N 1000000
	long long hailstone(long long n) {
	int count = 0;
	while (n != 1) {
	count++;
	(n % 2 == 0) ? (n = n / 2) : (n = (3 * n + 1));
	}
	return count;
	}
	int main() {
	long long count = 0, max = 0, ans = 0;
	for (register long long i = 1; i <= N; i++) {
	count = hailstone(i);
	if (max < count) { // 최댓값 갱신
	max = count;
	ans = i;
	// cout << ans << ": " << max << endl;
	}
	count = 0;
	}
	cout << ans << ": " << max << endl;
	return 0;
	}

view raw ProjectEuler_Problem14.cpp hosted with ❤ by GitHub

정답

837799

심화 공부

콜라츠 추측(Collatz Conjecture)

1937년에 처음으로 이 추측을 제기한 로타르 콜라츠 의 이름을 딴 것으로 3n+1 추측, 울람 추측, 혹은 헤일스톤(우박) 수열 등 여러 이름으로 불린다. 콜라츠 추측은 임의의 자연수가 다음 조작을 거쳐 항상 1이 된다는 추측이다.

1. 짝수라면 2로 나눈다.

2. 홀수라면 3을 곱하고 1을 더한다.

3. 1이면 조작을 멈추고, 1이 아니면 첫 번째 단계로 돌아간다.

예를 들어, 6 에서 시작한다면, 차례로 6, 3, 10, 5, 16, 8, 4, 2, 1 이 된다. 또, 27에서 시작하면 무려 111번을 거쳐야 1이 된다. 77번째에 이르면 9232를 정점으로 도달하다가 급격히 감소하여 34단계를 더 지나면 1이 된다.

이 추측은 컴퓨터로 268까지 모두 성립함이 확인되었다. 그러나, 아직 모든 자연수에 대한 증명은 발견되지 않고 있다. 이 문제의 해결에 500달러의 현상금을 걸었던 에르되시 팔 은 "수학은 아직 이런 문제를 다룰 준비가 되어 있지 않다."는 말을 남겼다.

---

문제 출처 : https://euler.synap.co.kr/problem=14