d라이브러리

아~! 이렇게 쉬워 보이는데 못 푼다는 말인가. 여러 후배 수학자를 좌절하게 한 ‘콜라츠 추측’. 나 오일러도 모르겠다~! 300년을 넘게 산 경험으로 봤을 때, 힘을 모으면 언젠가 그 진가가 발휘되지! 그래서 준비했다. 오일러 프로젝트!

당대 최고의 수학자도 풀지 못해 어렵기로 악명 높은 수학 문제 중 문제 자체는 초등학생도 이해할 수 있는 게 있다. 이번 호에 소개할 콜라츠 추측 역시 그중 하나로, 문제는 쉽지만 증명이 어려워 많은 수학자를 좌절하게 했다. 대표적인 수학자가 수소폭탄 개발자로 유명한 미국 수학자 스타니스와프 울람이다. 얼마나 열심히 연구했던지 콜라츠 추측을 ‘울람 추측’이라고도 부른다. 

콜라츠 추측은 독일 수학자 로타르 콜라츠가 1937년 처음 제기한 문제로, 자연수와 짝수, 홀수, 사칙연산 개념만 안다면 문제를 이해할 수 있다.

예를 들어 임의로 고른 수가 3이라면, 3은 홀수니까 ➋에 따라 10이 되고, 10은 1이 아닌 짝수이므로 ➊에 따라 5가 된다. 1이 될 때까지 이 같은 과정을 반복하면 총 7단계를 거쳐 1이 된다. 수를 하나 골라 콜라츠가 제안한 방법으로 1이 될 때까지 수를 줄여 나가 보자. 

그런데 홀수일 때 3을 곱하고 1을 더하지 않고 1을 빼면 더 빨리 1이 되지 않을까? 안타깝게도 5만 돼도 절대 1이 될 수 없다는 걸 알 수 있다(5→14→7→20→10→5). 5단계를 거치면 다시 5가 나와 끝없이 순환하기 때문이다. 

콜라츠 추측 역시 앞에 소개한 5처럼 순환하는 수를 하나라도 발견하면 틀린 게 된다. 그런데 컴퓨터의 힘을 빌려 계산한 결과 1부터 87×260까지 모든 수가 순환하지 않고 결국 1이 돼 참일 가능성에 무게가 실리고 있다. 

별명은 우박 수열

콜라츠 추측은 부르는 말이 참 많다. 앞에서 언급한 ‘울람 추측’ 외에도 ‘3n+1 추측’, ‘우박 수열’이라고도 부른다. 우박 수열에서 우박은 우리가 알고 있는 얼음 덩어리를 말한다. 콜라츠 추측에 따라 수를 나열하면 수가 커졌다가 작아졌다가 반복하다 어느 순간 1이 되는데, 그 모습이 마치 우박이 만들어져 바닥으로 떨어지는 과정과 비슷하다고 여겨 이름 붙인 것이다. 

그렇다면 얼마나 커졌다가 작아질까? 한 예로 27은 큰 수가 아니라서 금세 1이 될 것 같지만, 111단계를 거쳐야 1이 된다. 놀랍게도 77단계에선 자신보다 약 342배나 큰 9232까지 커졌다가 30여 단계를 더 거쳐 1이 된다. 

이처럼 예상치 못한 전개로 수가 커지고 작아져서인지 수학자뿐만 아니라 컴퓨터과학자까지 합세해 열심히 연구하고 있지만, 콜라츠 추측의 해결 기미는 아직까지 보이지 않고 있다. 헝가리의 천재 수학자 에르되시 팔 역시 500달러의 상금을 걸면서 “수학은 아직 이런 문제를 다룰 준비가 돼 있지 않다”고 말했을 정도다. 에르되시는 문제의 난이도에 따라 1달러부터 5000달러까지 상금을 걸었는데, 보통 100달러를 넘으면 아주 어려운 문제다. 

하지만 어려운 만큼 해결하면 단번에 유명해질 수 있다! 훗날 콜라츠 추측을 내 손으로 증명하는 꿈을 꿔보며 지금은 콜라츠 추측의 특수한 경우를 컴퓨터를 이용해 풀어 보자.

● 오일러 프로젝트 14번을 해결하려면?

오일러 프로젝트 14번 문제는 콜라츠 추측에서 처음 수가 1,000,000 이하일 때 1까지 도달하는 데 가장 긴 과정을 거치는 처음 수를 찾는 거예요. 물론 계산 과정 중에는 1,000,000을 넘어도 괜찮답니다.

콜라츠 추측을 해결하는 건 매우 어렵지만 14번 문제를 푸는 건 프로그래밍 난이도가 낮아 초보자도 쉽게 도전할 수 있어요. 다음 수가 무엇이 나올지 계산하면서 적절하게 ‘반복문(for문이나 while문)’을 만들기만 하면 되거든요. 

사실 어떤 코드를 짜냐에 따라 효과적인 프로그래밍 언어가 따로 있는데, 이 문제는 어떤 언어를 쓰더라도 코드에 큰 차이가 없어요. 다만 큰 수가 불쑥불쑥 튀어나오는 경우가 많으니 큰 수를 편하게 다룰 수 있는 언어라면 처리 속도를 높이는 데 도움이 되겠죠? 시작하는 수가 크지 않더라도 계산 도중 예상 밖의 큰 수가 나오는 경우가 종종 있거든요. 100억을 넘는 경우도 있답니다. 

그런 의미에서 언어를 추천하면 ‘파이썬’이나 ‘루비’가 쉽게 배울 수 있으면서 코드도 간결해서 좋아요. 종종 언어 특성 때문에 문제와 관련 없는 코드를 짜야 할 때가 있는데, 이 두 언어는 오로지문제에만 집중할 수 있어 좋답니다. 수학 문제 풀이에 유용하고 파이썬과 문법이 비슷한 ‘줄리아’도 괜찮겠네요.

나머지 연산을 활용하라!

이번 문제를 해결할 때 중요한 개념은 ‘나머지 연산’이에요. 대부분의 프로그래밍 언어에서 나머지 연산은 ‘%’ 기호로 나타냅니다. 예를 들어 n을 2로 나눈 나머지는 ‘n%2’로 쓰고, 3으로 나눈 나머지는 ‘n%3’으로 쓰지요. 

이 문제에서는 어떤 수 n이 짝수인지 홀수인지 알아내는 과정에서 나머지 연산을 활용할 수 있어요. ‘n%2’가 0이라면 n은 짝수이고, 1이라면 홀수예요. n이 홀수냐 짝수냐에 따라 각각 다른 값을 대입할 때 ‘조건문(if문)’을 주로 씁니다. 파이썬으로 예를 들면 오른쪽 코드와 같아요. n이 짝수일 때는 2로 나누고, 홀수일 때는 3n+1이라는 연산을 한다는 콜라츠 추측의 ➊, ➋ 과정을 나타낸 거랍니다.

프로그래밍 초보자라 조금 더 조언이 필요하다고요? 그렇다면 수학동아 블로그(mathdonga.blog.me) 해당 포스트에서 자세한 내용을 확인하세요. 오일러 프로젝트 사이트에 접속해 각 문제의 답을 입력하면, 정답을 맞힌 문제에 한해서 사람들이 달아놓은 댓글에서 다른 사람의 코드를 볼 수 있다는 사실도 알아두세요!