프로젝트 오일러 125번

The palindromic number 595 is interesting because it can be written as the sum of consecutive squares: \(6^2 + 7^2 + 8^2 +9^2 + 10^2 + 11^2 + 12^2\).

There are exactly eleven palindromes below one-thousand that can be written as consecutive square sums, and the sum of these palindromes is \(4164\). Note that \(1 = 0^2 + 1^2\) has not been included as this problem is concerned with the squares of positive integers.

Find the sum of all the numbers less than \(10^8\) that are both palindromic and can be written as the sum of consecutive squares.

---

palindromic number(좌우대칭인 수, 앞에서부터 보나 뒤에서부터 보나 같은 수) \(595\) 는 연속적인 수들의 제곱합 \(6^2 + 7^2 + 8^2 +9^2 + 10^2 + 11^2 + 12^2\) 으로 표현되는 재미있는 성질이 있다. \(1000\) 미만의 자연수 중 palindromic number 이면서 연속적인 수들의 제곱합으로 표현되는 수는 \(11\) 개가 있으며, 이들의 총합은 \(4164\) 이다. \(1 = 0^2 + 1^2\) 으로 표현할 수 있지만 자연수가 아닌 \(0\) 이 포함되어 있으므로 관심 대상에서 제외한다. \(10^8\) 미만의 수 중 palindromic number 이면서 연속적인 수들의 제곱합으로 표현되는 모든 수들의 총합을 구하시오. (\(4=2^2\) 같은 경우도 연속적인 수들의 제곱합이 아니므로 관심의 대상에서 제외한다.) 

이 문제를 간단하게 생각하면 1부터 \(10^8\) 까지 변화 시키면서 그 수가 일단 palindrome인지 확인하고, 다시 연속적인 자연수들의 제곱 합으로 나타낼 수 있는지 확인하여 조건을 만족한 수들을 모두 더해 가면 된다. 하지만 이렇게 할 경우 두 번째 조건을 확인하는데 상당한 시간이 소요된다. 프로젝트 오일러 문제들을 풀면서 여러 번 느끼는 것이지만 풀이법이 잘 떠오르지 않을 때는 역발상을 하게되면 실마리가 풀리는 경우가 많다.

125번 문제 역시 역발상을 통해 보다 쉽게 답을 구해낼 수 있다. 즉, palindrome으로 확인된 수가 연속적인 자연수들의 제곱합으로 표현될 수 있는지를 확인하는게 아니라, 연속적인 자연수들의 제곱합이 palindrome인지 확인하는 것이다.

이를 위해서 먼저 연속적인 자연수들의 제곱합을 구할 때, 가장 큰 수가 될 수 있는 수가 무엇인지 구해야 한다. 결론부터 말하자면 그 수는 \(10^4 - 1\) 이 되어야 한다. 왜냐하면 \(10^4\) 을 제곱하게 되면 \(10^8\) 이 되고 이는 자연수 하나의 제곱으로도 \(10^8\) 을 만들기 때문이다. 문제에 의하면 적어도 연속하는 자연수 두 개 이상의 합으로 표현 가능해야 한다. 따라서 우리가 연속적인 자연수 제곱합을 구할 때는 \(10^4\) 미만의 범위에서 구하면 된다.

다음은 가장 핵심적인 부분의 파이썬 코드이다.

result = set()
for i in range(1, int(math.sqrt(10 ** 8))):
    temp = i ** 2
    while temp < 10 ** 8:
        i += 1
        temp += i ** 2
        if palcheck(temp):  # palcheck 은 palindrome 인지 확인해 주는 함수이다.
            result.add(temp) 

코드에서 보듯이 1부터 \(n\) 까지의 연속적인 자연수들의 합이 palindrome인지 확인하여 만약 그렇다면 집합(set)으로 정의된 result에 그 값을 추가한다. (물론 \(n\) 은 \(10 ^4\) 미만의 수이다.)

다음 단계에서는 2부터 \(n\) 까지의 연속적인 자연수들의 합이 palindrome인지 확인하여 result에 값을 추가한다.

이런식으로 가능한 모든 연속적인 자연수 제곱합을 구하여 palindrome인지 확인한 후, result에 추가하는 방법으로 프로세스를 진행하면 보다 빠르게 답을 얻을 수 있다. 여기서 리스트(list)가 아닌 집합(set)을 사용한 이유는 연속적이 자연수 제곱의 합으로 표현하는 방법이  두 가지 이상인 수들이 있기 때문이다. 확인해 볼 결과 \(10 ^8\) 미만에서 이런 수들이 2 개 있는것 같다. 여하튼 같은 수가 result에 두 번 이상 추가되는 것을 방지하기 위해서 집합(set)을 이용하였다.