Euler Problem 14

문제의 내용

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.

단순히 위해서 설명된 규칙대로 구현하였다. 백만까지의 숫자들을 시작점으로 하여 위 규칙을 적용하여 가장 많은 항들이 나타나는 것을 체크하였다. 논리는 쉬우나, 막상 구현된 것의 실행시간은 매우 느렸다. 더 빠른 방법을 연구하여 보아야 한다.

Sub Euler14()
    Dim Maxcount, MaxStartNum
    Dim n, count, i
    For i = 500000 To 1000000
        count = 1 ' 시작하는 수를 첫항으로 포함
        n = i  ' Starting Number
        Do While n > 1
            If Mod2(n, 2) = 0 Then
                n = n / 2
            Else
                n = 3 * n + 1
            End If
            count = count + 1
        Loop
        If count > Maxcount Then
            Maxcount = count
            MaxStartNum = i
        End If
    Next
    Debug.Print Maxcount & "번", MaxStartNum
End Sub

' mod 함가 오버플로가 발생하여 이 함수를 대체한다.
Function Mod2(ByVal Num, ByVal Divide)
    Dim Mok
    Mok = Int(Num / Divide)
    Mod2 = Num - (Mok * Divide)
End Function