파이썬으로 콜라츠 추측 알고리즘 구현하기

콜라츠 추측에 대한 자세한 설명은 이 내용에 대한 위키피디아를 참고해보세요. (새 창에서 열립니다.)

간단하게 추리면, 어떠한 임의의 자연수를 구하고 그 자연수가 짝수면 2로 나누고, 홀수면 3을 곱하고 1을 더하는 것을 그 자연수가 1이 될 때까지 반복하는 것입니다.

모든 자연수가 이 과정을 거치면 1이 된다고 추측하고 있고, 컴퓨터로 2의 68제곱까지 증명되었지만 진짜 모든 자연수가 이 과정을 거쳐서 1이 되는지 증명되지 않았습니다.

 

매우매우 흥미로운 주제입니다.

그래서 이 추측을 파이썬으로 구현해보기로 했습니다.

저의 좁쌀만한 코딩 실력으로 말이죠.

 

알고리즘은 이렇습니다.

 

1. number 변수를 임의의 자연수로 지정한다.

2. while 반복문으로 무한루프를 만든다.

3. number 변수가 짝수면 2로 나누고, 홀수면 3을 곱하고 1을 더하는 것을 그 자연수가 1이 될 때까지 반복한다.

4. 반복이 끝나면 텍스트를 출력한다.

5. 3, 4번 과정을 무한반복한다.

 

위 알고리즘을 구현한 파이썬 소스코드입니다.

print("콜라츠 추측을 파이썬으로 구현하기.")

number = 2 #아무 자연수나 지정해보세요. 2의 68제곱도 가능합니다만, 너무 큰 수는 오류가 납니다.
x = 0

while True:
    x = number
    
    while x != 1:
        if x%2 == 1:
            x = x*3 + 1
        else:
            x = x/2


    print(str(number) + ", True")
    number += 1

꽤 간단합니다.

실행 결과는 다음과 같습니다.

점점 수가 커지지만, 모두 정상적으로 출력되는 것을 볼 수 있습니다.

제가 실험해 본 결과, 2의 68제곱 이상도 가능하더라고요.

2의 688제곱도 해봤는데 됩니다.

단, 너무 크면 오류가 납니다. 너무 큰 수라고 뜨면서요.

 

실행속도가 느린 언어라고 유명한 파이썬이지만, 역시 컴퓨터는 컴퓨터입니다.

저라면 한세월 흘렀을 것을 1초도 안되어 출력하네요.

 

도움이 되셨다면 공감 한번씩 눌러주시고, 도움이 안되셨다면 공감 한번씩 눌러주시면 감사하겠습니다!