Project Euler #55 - Lychrel numbers

프로젝트 오일러 55번 - Lychrel 수
많은 경우, 어떤 수에다가 자기자신을 뒤집은 수를 더하는 과정을 반복하면 palindrome(뒤집어도 자기 자신인 수)가 된다. 예외적인 수를 Lychrel수라고 하는데, 이론적으로 증명할 수는 없지만, 위의 과정을 50번 반복해도 palindrome이 안 된다면 영원히 안 되는 것으로 간주해도 된다. 10000 보다 작은 Lychrel수는 몇 개?

문제는 길지만 풀이 과정은 짧다. 중간에 cache역할 하는 dict를 넣어봐도 시간이 별로 줄지 않는다.

def Lychrel(n):
    for i in range(50):
        n = n + int(str(n)[::-1])
        if str(n) == str(n)[::-1]:
            return False
    return True

rs = 0
for i in range(1,10000):
    if Lychrel(i): rs += 1

print rs