(Java) Project Euler 014 - Longest Collatz Sequence

// The following iterative sequence is defined for the set of positive integers:

// n -> n/2 (n is even)
// n -> 3n + 1 (n is odd)

// Using the rule above and starting with 13, we generate the following sequence:

// 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1.

// It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms.
// Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

// Which starting number, under one million, produces the longest chain?

// NOTE: Once the chain starts the terms are allowed to go above one million

 

Question)

-- 양의 정수 집합에 대해 다음과 같은 반복 시퀀스를 정의할 수 있다.

-- n -> n/2 (n은 짝수)
-- n -> 3n + 1 (n은 홀수)
-- 위의 규칙을 사용하고 13부터 시작하여 다음 시퀀스를 만들 수 있다.
-- 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1.
-- 이 시퀀스(13에서 시작하여 1에서 끝남)에는 10개의 수가 포함되어 있음을 알 수 있다.
-- 아직 증명되지 않았지만(콜라츠 문제) 모든 시작 숫자가 1로 끝나는 것으로 보여진다.
-- 100만 미만의 시작 숫자 중 가장 긴 체인을 생성하는 숫자는 무엇인가?
-- 참고: 체인이 시작되면 숫자는 백만을 초과할 수 있다.

 

 

import java.util.ArrayList;

public class ProjectEuler_014 {
    public static void main(String[] args) {

        int maxLength = 2;
        int result = 0;

        for (int i = 2; i < 1000000; i++) {                                     //  1)
            int length = getSequence(i).size();

            if (length > maxLength) {                                           //  2)
                maxLength = length;
                result = i;
            }
        }

        System.out.println("The number with the longest collatz sequence below one million is : " + result);
        System.out.println("The length of sequence is : " + maxLength);
    }

    static long processOdd(long odd) {                                          //  3)
        return 3 * odd + 1;
    }

    static long processEven(long even) {                                        //  4)
        return even / 2;
    }

    static long process(long sequenceNumber) {                                  //  5)
        if (sequenceNumber % 2 == 0) {
            return processEven(sequenceNumber);
        } else {
            return processOdd(sequenceNumber);
        }
    }

    static ArrayList<Long> getSequence(long startNum) {                         //  6)
        ArrayList<Long> theSequence = new ArrayList<>();
        
        while (startNum > 1) {                                                  //  7)
            theSequence.add(startNum);
            startNum = process(startNum);
        }

        return theSequence;
    }
}

 

1) 1부터 999,999까지의 모든 숫자에 대해 시퀀스의 길이를 계산.
2) 현재까지의 최대 길이보다 더 긴 시퀀스가 나오면 업데이트하기. result에는 시퀀스의 시작 숫자 저장.
3) 홀수인 경우 3을 곱하고 1을 더함.
4) 짝수인 경우 2로 나눔.
5) 홀수/짝수에 맞는 수열 처리.
6) 주어진 시작 숫자(startNum)로부터 생성된 시퀀스를 반환.
7) 1보다 큰 동안 시퀀스를 계속 생성.