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

사이트 이름 - 문제 14번

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

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

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

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

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

아직 증명은 되지 않았지만, 이런 과정을 거치면 어떤 수로 시작해도 마지막에는 1로 끝나리라 생각됩니다.
(역주: 이것은 콜라츠 추측 Collatz Conjecture이라고 하며, 이런 수들을 우박수 hailstone sequence라 부르기도 합니다)

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

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

해결 방법

홀수 일 때, 짝수 일 때 각각 계산하는 식을 만들고, 반복문이 실행될 때 마다 카운트를 해서 그 카운터가 가장 클 때 출력(저장)하면 될거 같다.

maximum = 0 # 계산 횟수를 저장할 변수
result = 0  # 최대 계산 횟수일 경우 어떤 수에서 발생했는지 저장하는 변수

for i in range(2, 1000001):
    counter = 1 # 카운터는 매번 반복문이 다시 실행될 때 초기화 되어야 한다.

    j = i # i각 계속 연산되어야 하므로 따로 변수 j를 주어 i는 보존
    while True:
        if j == 1: # 계산 결과가 1이 되면 다음 숫자로 넘어가야 해서 while문 종료
            if maximum < counter: # 최댓값일 때 변수에 기록
                maximum = counter
                result = i

            break # while 문 종료

        counter += 1

        if j % 2 == 0:
            j = j / 2
        else:
            j = 3 * j + 1


print(result, maximum)  # 525회 계산을 하는 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이 된다.

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

• 위키백과, 콜라츠 추측
• Wikipedia, Collatz conjecture
• MathWorld, Collatz Problem

다른이의 해결 방법

아래 방법으로 처리하면 수 초 안에 완료된다.

생각보다 딕셔너리가 성능이 좋은건가??? 아직 딕셔너리를 공부하지 않아서 모르겠다. 공부해야겠다...쩝

dictionary=dict()
for n in range(1,1000001):
    num=n
    cnt_now=0
    while True:
        if n==1:
            cnt_now+=1
            break
        if n in dictionary:
            cnt_now=cnt_now+dictionary[n]
            break
        if n%2==0:
            n=n/2
        else:
            n=3*n+1
        cnt_now+=1
    dictionary[num]=cnt_now

print(max(dictionary,key=dictionary.get))