IT/모바일
저자: 한동훈(traxacun at unitel.co.kr)
우박수 이야기만큼 출처가 불분명한 수학적 문제가 없다고 합니다. 이 문제는 출판된 적도 없으며, 수학자들 사이에서 편지로 오간적도 없습니다. 어떤 사람들은 이 문제를 "3N + 1" 문제라고도 합니다. 숫자가 홀수일 때는 그 수에 3을 곱한 후 1을 더하며, 짝수일 때는 2로 나누기 때문입니다. 혹자는 콜라츠 문제라고도 하는데, 1930년 대에 로타르 콜라츠(Lothar Collatz)라는 학생이 이 문제를 창안했다고 주장하면서 붙은 이름입니다. 우박수라는 용어는 비교적 최근에 생겨난 것입니다.
1950년대 이전에는 이 문제에 대한 논문도 없었습니다. 그러던 것이 관심이 점점 커지면서 1970년 대에는 이 문제에 각종 상금이 걸리기 시작했고, 무수한 증명들이 등장했지만 모두 틀렸다는 것이 밝혀졌습니다.
우박수 문제의 정의는 믿을 수 없을 만큼 쉬우면서도 풀리지 않는 문제를 낳는데 이 문제는 앞으로도 오랫동안 풀리지 않을 것이라고 합니다.
우박수 문제의 정의, "N이 홀수일 때는 3N + 1을 하고, N이 짝수일때는 N/2"에 따르면 수열은 다음과 같은 형태가 됩니다.
1, 2, 3으로 시작하는 수열에서 보는 것처럼 곧 142142142라는 순환마디가 나타납니다. 조금 더 큰 수 7로 시작하는 수열은 다음과 같습니다.
이번에는 수열이 조금 더 길어지고 52라는 조금 큰 수까지 나아가지만, 그 후로는 다시 작은 수로 무너지면서 결국에는 142142라는 순환마디가 영원히 반복됩니다.
그렇다면 조금 더 긴 수열을 찾아내려면 전략을 세워야 합니다. 일단, (1)짝수는 정의에 따라 절반으로 줄어들기 때문에 고려 대상에서 제외합니다. 그렇다면 조금 더 큰 (2)홀수를 찾아야 합니다. (3) 순환마디라는 것은 같은 수가 나와서는 안되는 것을 의미합니다. 같은 수가 나오면 그때부터 순환마디가 반복되는 것입니다. 7로 시작하는 수열에서 보면 22, 11, 34, 17등의 수는 모두 고려 대상에서 제외됩니다. 왜냐하면, 22로 시작하는 수열은 이미 7로 시작하는 수열의 부분집합이기 때문입니다. 이와 같이 고려해보면 27이라는 홀수를 고려해볼 수 있습니다. 27로 시작하는 수열은 보다 더 긴 수열의 형태를 보여줍니다.
39번째 수(38번째 단계)에서 1000의 장벽을 무사히 뛰어넘고, 수열은 계속 커지는 것처럼 보입니다. 수열은 점점 커져서 77번째 단계에서는 9232에 이르게 되지만, 그 다음부터는 붕괴하기 시작합니다.
111번째 단계에서는 결국 1에 이르게 되고, 142142라는 순환마디가 시작됩니다. 이들 수의 전체 여행을 그래프로 나타내면 다음과 같습니다.
[그림] 27에서 시작한 우박수의 수열
우박수라는 이름은 바로 이러한 종류의 그림에서 나왔습니다. 수열 속의 수들이 올라갔다 내려갔다 하는 양상이 뇌운속에서 우박이 성장하면서 오르락 내리락 하는 모습과 비슷합니다. 뇌운 속의 우박이 계속 성장하다가 상승기류가 그 무게를 떠받치지 못해 추락하는 것처럼 우박수 문제도 142142..라는 순환마디로 붕괴하고 맙니다.
모든 수가 결국에는 142 순환마디로 붕괴하고 마는 것일까? 이 문제에 대해서 1989년 도쿄대학에서 1조에 이르는 모든 수를 시험했고 모두 142142... 순환마디로 붕괴한다는 사실을 밝혀냈습니다.
지금도 우박수 문제에 대해서는 142로 붕괴하지 않는 수를 찾아내기 위한 다양한 가정이 세워지고 있습니다. 혹자들 사이에서 이 문제는 수학자들의 진지한 수학 연구를 방해하려는 국제적 음모라고 이야기 하기도 합니다.
Programming Challenges의 첫번째 문제가 3n + 1 문제로 시작합니다. 이 문제에서는 1부터 1,000,0000 사이의 숫자들 중에서 최대의 사이클을 갖는 수를 찾아내는 것입니다. 시작수가 26623의 경우 307 단계를 거치며, 77031은 350단계를 거칩니다. 77031은 10만 아래의 수 중에서 가장 긴 단계를 가집니다. 77671은 10만 아래의 수에서 가장 높은 봉우리 수인 1570824736을 갖습니다.
프로그래밍을 통해 만약 여러분이 142로 붕괴하지 않는 수를 찾아낸다면 여러분의 이름을 영원히 남길지도 모릅니다. ^^
참고자료
우박수 이야기만큼 출처가 불분명한 수학적 문제가 없다고 합니다. 이 문제는 출판된 적도 없으며, 수학자들 사이에서 편지로 오간적도 없습니다. 어떤 사람들은 이 문제를 "3N + 1" 문제라고도 합니다. 숫자가 홀수일 때는 그 수에 3을 곱한 후 1을 더하며, 짝수일 때는 2로 나누기 때문입니다. 혹자는 콜라츠 문제라고도 하는데, 1930년 대에 로타르 콜라츠(Lothar Collatz)라는 학생이 이 문제를 창안했다고 주장하면서 붙은 이름입니다. 우박수라는 용어는 비교적 최근에 생겨난 것입니다.
1950년대 이전에는 이 문제에 대한 논문도 없었습니다. 그러던 것이 관심이 점점 커지면서 1970년 대에는 이 문제에 각종 상금이 걸리기 시작했고, 무수한 증명들이 등장했지만 모두 틀렸다는 것이 밝혀졌습니다.
우박수 문제의 정의는 믿을 수 없을 만큼 쉬우면서도 풀리지 않는 문제를 낳는데 이 문제는 앞으로도 오랫동안 풀리지 않을 것이라고 합니다.
우박수 문제의 정의, "N이 홀수일 때는 3N + 1을 하고, N이 짝수일때는 N/2"에 따르면 수열은 다음과 같은 형태가 됩니다.
1, 4, 2, 1, 4, 2, 1, 4, 2, ...
2, 1, 3, 2, 1, 4, 2, 1, 4, 2, ...
3, 10, 5, 16, 8, 4, 2, 1, 4, 2, ...
1, 2, 3으로 시작하는 수열에서 보는 것처럼 곧 142142142라는 순환마디가 나타납니다. 조금 더 큰 수 7로 시작하는 수열은 다음과 같습니다.
7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1...
이번에는 수열이 조금 더 길어지고 52라는 조금 큰 수까지 나아가지만, 그 후로는 다시 작은 수로 무너지면서 결국에는 142142라는 순환마디가 영원히 반복됩니다.
그렇다면 조금 더 긴 수열을 찾아내려면 전략을 세워야 합니다. 일단, (1)짝수는 정의에 따라 절반으로 줄어들기 때문에 고려 대상에서 제외합니다. 그렇다면 조금 더 큰 (2)홀수를 찾아야 합니다. (3) 순환마디라는 것은 같은 수가 나와서는 안되는 것을 의미합니다. 같은 수가 나오면 그때부터 순환마디가 반복되는 것입니다. 7로 시작하는 수열에서 보면 22, 11, 34, 17등의 수는 모두 고려 대상에서 제외됩니다. 왜냐하면, 22로 시작하는 수열은 이미 7로 시작하는 수열의 부분집합이기 때문입니다. 이와 같이 고려해보면 27이라는 홀수를 고려해볼 수 있습니다. 27로 시작하는 수열은 보다 더 긴 수열의 형태를 보여줍니다.
27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, ...
39번째 수(38번째 단계)에서 1000의 장벽을 무사히 뛰어넘고, 수열은 계속 커지는 것처럼 보입니다. 수열은 점점 커져서 77번째 단계에서는 9232에 이르게 되지만, 그 다음부터는 붕괴하기 시작합니다.
9232, 4616, 2308, 1154, 577, 1732, 866, 433, ...
111번째 단계에서는 결국 1에 이르게 되고, 142142라는 순환마디가 시작됩니다. 이들 수의 전체 여행을 그래프로 나타내면 다음과 같습니다.
[그림] 27에서 시작한 우박수의 수열
우박수라는 이름은 바로 이러한 종류의 그림에서 나왔습니다. 수열 속의 수들이 올라갔다 내려갔다 하는 양상이 뇌운속에서 우박이 성장하면서 오르락 내리락 하는 모습과 비슷합니다. 뇌운 속의 우박이 계속 성장하다가 상승기류가 그 무게를 떠받치지 못해 추락하는 것처럼 우박수 문제도 142142..라는 순환마디로 붕괴하고 맙니다.
모든 수가 결국에는 142 순환마디로 붕괴하고 마는 것일까? 이 문제에 대해서 1989년 도쿄대학에서 1조에 이르는 모든 수를 시험했고 모두 142142... 순환마디로 붕괴한다는 사실을 밝혀냈습니다.
지금도 우박수 문제에 대해서는 142로 붕괴하지 않는 수를 찾아내기 위한 다양한 가정이 세워지고 있습니다. 혹자들 사이에서 이 문제는 수학자들의 진지한 수학 연구를 방해하려는 국제적 음모라고 이야기 하기도 합니다.
Programming Challenges의 첫번째 문제가 3n + 1 문제로 시작합니다. 이 문제에서는 1부터 1,000,0000 사이의 숫자들 중에서 최대의 사이클을 갖는 수를 찾아내는 것입니다. 시작수가 26623의 경우 307 단계를 거치며, 77031은 350단계를 거칩니다. 77031은 10만 아래의 수 중에서 가장 긴 단계를 가집니다. 77671은 10만 아래의 수에서 가장 높은 봉우리 수인 1570824736을 갖습니다.
프로그래밍을 통해 만약 여러분이 142로 붕괴하지 않는 수를 찾아낸다면 여러분의 이름을 영원히 남길지도 모릅니다. ^^
참고자료
- 놀랄만한 수학 아이디어와 문제들(Think of a number), 맬컴 E 라인스, 가람기획
- 수학의 미해결문제
- 이미 해결된 난제들
TAG :
이전 글 : 싱글톤을 이용한 네트워크 관리 패턴
다음 글 : 흔들리는 마이크로소프트의 아성
최신 콘텐츠