오일러 프로젝트 55

47이란 숫자를 골라서 뒤집은 다음 다시 원래 수에 더하면 47 + 74 = 121과 같이 대칭수(palidrome)가 됩니다. 물론 모든 숫자가 이토록 쉽게 대칭수를 만들어내지는 않습니다. 예를 들어 349의 경우에는

• 349 + 943 = 1292
• 1292 + 2912 = 4213
• 4213 + 3124 = 7337

위에서 보는 것처럼 3번의 반복과정을 거쳐야 대칭수가 됩니다. 196과 같은 몇몇 숫자들은 이와 같은 과정을 아무리 반복해도 대칭수가 되지 않을 것이라고 추측되는데, 이런 수를 라이크렐 수라고 부릅니다. 아직 증명되지는 않았지만, 문제 풀이를 위해서 일단 라이크렐 수가 존재한다고 가정을 하겠습니다.

또한 1만 이하의 숫자들은 50번 미만의 반복으로 대칭수가 되든지 라이크렐 수이든지 둘 중 하나라고 합니다. 1만을 넘어서면 10677에 이르렀을 때 비로소 53번의 반복으로 4668731596684224866951378664라는 28자리의 대칭수가 만들어집니다.

그러면 1만 이하에는 몇 개의 라이크렐 수가 존재합니까?

http://euler.synap.co.kr/prob_detail.php?id=55

접근

문제가 길지만 사실 간단한 내용이다. 1만 이하의 수 중에서 라이크렐 수의 개수를 세면 된다. 어떤 수가 라이크렐 수인지를 판별하는 함수를 하나 작성하자. 라이크렐 수는 다음과 같이 판단한다.

1. 원래의 수와 그 숫자를 뒤집은 수를 더한다.
2. 더한 결과가 대칭수(palindrome)인지 판단한다. 대칭수가 되면 라이크렐 수가 아니다.
3. 1~2의 과정을 50회까지 반복하는 동안 대칭수가 아니라면 라이크렐 수로 판정한다.

이 과정을 코드로 옮기면 되기에 매우 간단하다.

def test(n: int) -> bool:
  for _ in range(50):
    n += int(str(n)[::-1])
    if str(n) == str(n)[::-1]:
      return False
  return True

print(sum(1 for n in range(10_000) if test(n + 1)))

배열을 사용하는 방법

큰 수를 사용하지 않으려면 이 문제를 어떻게 풀 수 있을까? 정수를 각 자리 숫자(정수)의 배열로 표현하면 처리할 수 있다. 덧셈을 구현하는 부분이 조금 까다롭게 느껴질 수 있지만, 더하는 두 수가 자릿수가 같고, 거꾸로 된 수이기 때문에 역순으로 더해도 결과가 동일하기 때문에 예전에 작성해본 s_add() 함수보다 오히려 간단할 수 있다.

from math import log10

def digits(n: int) -> list[int]:
    '''정수를 각 자릿수 숫자의 배열로 변환'''
    l = int(log10(n) + 1)
    return [(n // 10**(l-i-1)) % 10 for i in range(l)]

def ispal(xs):
    '''정수배열이 대칭인지를 검사'''
    l = round(len(xs) / 2)
    return xs[:l] == xs[len(xs)-1:-l-1:-1]

def test(n):
    ds = digits(n)
    for _ in range(50):
        es = []
        z = 0
        for x, y in zip(ds, ds[::-1]):
            z, w = divmod(x + y + z, 10)
            es.append(w)
        if z > 0:
            es.append(z)
        if ispal(es):
            return False
        ds = es[::-1]
    return True

print(sum(1 for n in range(10000) if test(n + 1)))