프로젝트 오일러 052
2배, 3배, 4배, 5배, 6배를 하여도 같은 숫자로 이루어지는 가장 작은 수
문제에서 직접적으로 주어진 단서가 많이 없기 때문에 고민이 제법 필요한 문제입니다. 먼저 순열인 수들의 성질에 대해 좀 살펴 보겠습니다. 사실 아주아주 신기하고 재밌는 문제이기도 합니다.
순열인 수들
123, 321, 213 과 같이 같은 숫자들이 순서만 다르게 조합되어 있는 수들은 마치 1, 2, 3으로 만들 수 있는 순열과 같습니다. 실제로 이렇게 부르는 지는 잘 모르겠습니다만, 편의상 이러한 수들을 ‘순열인 수들’이라고 칭하겠습니다.
순열인 두 수에서 서로 다른 위치에 있는 같은 숫자들이 나타내는 실제 값은 얼마나 차이가 날까요?
- 3 -> 300 - 30 = 270 = 3 × (100 - 10) = 3 × 90
- 2 -> 20 - 2 = 18 = 2 × (10 - 1) = 2 × 9
- 1 -> 100 - 1 = 99 = 1 × (100 - 1) = 1 × 99
모든 숫자들은 자리를 바꾸면 9의 배수만큼 차이가 납니다. 결국 순열인 수들의 차는 9의 배수가 난다고 볼 수 있습니다. 어떤 수를 두 배했을 때 순열인 수가 된다면, 그 수 자체가 9의 배수가 되어야 한다는 이야기입니다.
제약 조건
우선 ‘가장 작은’이라는 단서가 붙었기 때문에 수를 구성하는 숫자의 개수가 최소가 되어야 한다는 점을 유념하고 접근하겠습니다.
지금까지는 9의 배수여야 한다는 것만 알고 있는데, 이것으로는 범위를 알아내기가 어렵습니다. 좀 더 범위를 좁힐 수 있는 단서가 필요합니다. 우선 6배까지 순열인 수가 나타난다고 했습니다. 순열인 수가 되려면 자릿수도 동일해야 합니다. 따라서 앞자리 숫자가 충분히 작아야 합니다. 11···, 12··· 이런 식으로 시작하는 수들이 유리합니다. 실제로 17 × 2 = 102이기 때문에 앞자리는 16까지는 허용이 될 수 있습니다.
각 자리 숫자의 끝자리는 2배, 4배하면서 계속 바뀌게 됩니다. 이 숫자들은 결국 다른 위치에서도 모두 등장해야 한다는 이야기가 됩니다. 1의 자리 숫자가 1, 2, 3,·· 일 때의 상황을 가정하고 조사해보겠습니다.
끝자리 수가 1이라면 배수들의 끝자리는 1, 2, 3, 4, 5, 6이고 앞자리 1,2가 더 필요하므로 최소 7개의 숫자가 필요합니다. 어느 정도 범위가 정해지는 느낌입니다. 다른 수들도 좀 더 살펴보겠습니다.
- 끝자리가 2라면 배수의 끝자리는 2, 4, 6, 8, 9, 0 이 등장합니다. 그리고 앞자리는 1, 2이어야하고, 9의 배수가 되려면 숫자가 더 필요합니다. 최소 8자리 수여야 합니다.
- 끝자리가 3이라면 배수의 끝자리는 6, 9, 2, 5, 8이 나옵니다. 앞자리에는 1, 2 혹은 1, 4가 와야 하므로 최소 7자리 수가 되어야 합니다.
- 끝자리가 5라면 배수의 끝자리는 5, 0이 반복됩니다. 하지만 5의 배수가 되면 +1, +2, +3이 순차적으로 올림으로 하고 앞에 있는 숫자들을 생각할 때, 1, 2, 3, 4, 5,6 이 모두 필요할 수 있습니다. 최소 8자리 수가 필요합니다.
- 끝자리가 7이라면 1~6배한 1의 자리는 7, 4, 1, 8, 5, 2로 6개가 됩니다. 그리고 이 6개는 그 합이 9의 배수이며, 여기에 앞자리 숫자 구현에 필요한 값들도 모두 포함되어 있습니다. 즉 1####7이고, 이 사이에는 2, 4, 5, 8 의 순열이 채워지는 값이라면 가능성이 있습니다!
- 끝자리가 8이면 배수의 끝자리는 8, 6, 4, 2, 0, 8입니다. 단, 2배했을 때 올림이 발생해서 홀수가 추가되기 때문에 결국 7자리 이상의 수가 됩니다.
- 끝자리 수가 9이면 배수의 끝자리는 9, 8, 7, 6, 5, 4이고 최소 7자리 이상이 필요합니다.
결국 1로 시작하며 7로 끝나는 6자리 수 중에서 답이 나올 수 있을 것 같습니다. 가운데 네 자리는 (2, 4, 5, 8)의 순열로 채워서 검사해보면 되겠습니다.
from itertools import permutations
def main():
# 각 자리 수로 분해하기
digits = lambda n: tuple(map(int, str(n)))
for ws in permutations([2, 4, 5, 8]):
ds = (1, *ws, 7)
n = int(''.join(str(d) for d in ds))
if n % 9 > 0:
continue
m = sorted(digits(n))
if all(m == sorted(digits(n * i)) for i in range(2, 7)):
print(n)
return
main()