Euler Problem 16

문제

2¹⁵ = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.
What is the sum of the digits of the number 2¹⁰⁰⁰?

컴퓨터 또는 프로그래밍 언어가 유효 자릿수를 충분히 제공하면 쉽게 계산할 수 있는 문제이다. 그러나 2의 1000제곱은 약 335자리수가 나올 것으로 예상되기 때문에 쉽게 생각할 수 없는 문제이다. (2^n일 경우, 보통 n이 +3마다 자리수가 +1 되므로 약 335자리가 예상됨). 그래서 10자리 숫자로 구분하여 배열에 할당하고, 이를 토대로 계산하는 알고리즘을 구상하였다. 생각보다 매우 빠르게 계산되어졌다. VBA에서도 유효자리수의 한계(15자리)를 이런 방식으로 극복할 수 있다.

Sub Euler16()
    Dim Num(1 To 35) As Double  ' 2^n일 경우, 보통 n이 +3마다 자리수가 +1 되므로 약 334자리가 예상됨. 대략 350자리로 하고 이를 10으로 나눔.
    Dim temp, upNum, i, j, strNum, Sum
    upNum = 0
    Num(35) = 1
    For i = 1 To 1000
        For j = 35 To 1 Step -1
            temp = Num(j) * 2 + upNum
            upNum = Int(temp / 10000000000#)
            Num(j) = temp - (upNum * 10000000000#)
            ' Debug.Print i, j, Num(j), upNum
        Next
    Next
    ' strsum 변수에 배열 Sum의 1번 배열 값을 입력한다.
    strNum = Num(35)
    ' strsum 변수에 나머지 배열 Sum의 값들을 10자리씩 형식을 지정하여 문자열로 연결하여 입력한다.
    For j = 35 To 1 Step -1
        strNum = Format(Num(j), "0000000000") & strNum
    Next
    Sum = 0
    For i = 1 To 350
        Sum = Sum + Mid(strNum, i, 1)
    Next
    ' 왼쪽에서 10개 자리에 있는 숫자들을 출력한다.
    Debug.Print Sum
End Sub