[수학 퍼즐 / java] 06.콜라츠 추측

안녕하세요.

이번 포스팅은 프로그래머의 뇌를 단련하는 수학퍼즐 6번문제인 콜라츠 추측을 풀어보겠습니다

 

 

 

 

지금까지 미결로 남아 있는 수학 문제 중에 콜라츠 추측(Collatz Conjecture)이 있다.

​

자연수 n에 대하여

​

- n이 짝수인 경우, n을 2로 나눈다.

​

- n이 홀수인 경우, n에 3을 곱해 1을 더한다.

​

이 계산을 반복하면 초깃값이 어떤 수였더라도 반드시 1에 도달한다.

​

(1 → 4 → 2 → 1과 같이 반복)

​

​

​

이 내용을 조금 바꾸어 초깃값이 짝수면 맨 처음에만 n에 3을 곱하여 1을 더하는 것에서 시작하기로 하고 '맨 처음의 수'로 돌아가는 법을 생각해본다.

​

​

​

예를 들어 2로 시작하는 경우에는 다음과 같다

​

2 → 7 → 22 →11 → 34 → 17 →52 → 26 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2

​

마찬가지로 4로 시작하면 다음과 같다

​

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

​

그러나 6으로 시작하면 다음과 같이 되어 6으로 돌아가지 않는다.

​

6 → 19 → 58 → 29 → 88 → 44 → 22 → 11 → 34 → 17 → 52 → 26 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 → 4 → ...

​

​

​

문제

​

10,000 이하의 짝수 중 위의 2나 4와 같이 '처음의 수로 돌아가는 수'가 몇 개 있는지 구해보시오.

 

package collatzConjecture;

import java.util.ArrayList;

public class CollatzConjecture {
    public static void main(String[] args) {
        ArrayList<Integer> arrList = new ArrayList<>();
        int i = 2;
        do {
            int n = i;
            n = 3 * n + 1;
            
            do {
                if (n % 2 == 0) n = n / 2; 
                else n = 3 * n + 1;

                if (n == i || n == 1) break;
            } while (true);
            
            if (n == i) arrList.add(n);
            i = i +2;
        } while (i <= 10000);

        int count=0;
        for(int r : arrList) {
            System.out.print(r + " ");
            count++;
        }
        
        System.out.println("\n" + count + "가지");
    }
}

2 4 8 10 14 16 20 22 26 40 44 52 106 184 206 244 274 322 526 650 668 790 866 976 1154 1300 1438 1732 1780 1822 2308 2734 3238 7288

정답 : 34가지