125874를 2배하면 251748이 되는데, 이 둘은 같은 숫자로 이루어져 있고, 순서만 다릅니다. 2배, 3배, 4배, 5배, 6배의 결과도 같은 숫자로 이루어지는 가장 작은 수는 무엇입니까?
http://euler.synap.co.kr/prob_detail.php?id=51
접근
프로젝트 오일러의 문제들 중에는 같은 숫자들이 순서만 다른, 즉 같은 숫자들의 순열인 값들에 대한 문제가 종종 나온다. 같은 숫자들의 순열인 값들은 흥미롭게도 그 차이가 9의 배수가 된다는 것이다.
두 자리 숫자 “AB”는 A * 10 + B 로 표현할 수 있는데, 순서를 바꾼 10 * B + A 와의 차이를 보면 결국 9 * A – 9 * B 가 된다. 세자리, 네자리수에서도 비슷하게 10의 거듭제곱만큼 차이가 있으니 차이는 모든 숫자의 차이는 9의 배수가 되고 그 차이의 합 역시 9의 배수가 된다.
어떤 수를 2배, 3배, 4배 한다는 것은 그 배수들의 차이가 자기 자신이라는 말로, 즉 문제의 조건을 만족하는 모든 수는 9의 배수라는 점을 알 수 있다. 그 외에 숫자들의 구성에서도 제약 사항이 있을까? 우선 6배 할 때까지 같은 순열이 되려면 숫자의 개수가 변하지 않아야 한다. 따라서 앞부분의 숫자가 적당히 작은 값이어야 한다. 6배 했을 때까지 자리수가 변하지 않으려면 12, 13, 14, 15, 16 중 하나로 시작해야 한다. (11은 두 배하면 22가 돼버림)
그리고 끝자리를 생각해보자. 2배, 3배, …, 6배 하는 동안 끝자리 숫자가 어떻게 변할까?
- 끝자리가 2라면, 배수의 끝자리에는 4, 6, 8, 0 이 등장한다. 그리고 올림하는 수가 생기면 홀수도 필요하기 때문에 너무 많은 숫자가 필요하다. 따라서 끝자리가 2가 될 확률은 적은 편이다.
- 끝자리가 5라면 끝자리는 0, 5가 반복된다. 9의 배수를 만들기 위해서는 1,2,4,8이 추가로 필요한데, 10의 자리에 오는 수들에 대해서 +1, +2, +3이 되어야 하므로, 홀수가 2개 더 필요할 수 있다. 즉 필요한 숫자는 최소 7개 이상이 되어야 한다.
- 끝자리가 3이라면? 3, 6, 9, 2, 5, 8 이 순서대로 오게 된다. 앞자리에 1이 와야 한다는 조건까지 최소 7자리가 된다.
- 끝자리가 7이라면? 7, 4, 1, 8, 5, 2 가 순서대로 오는데, 앞자리에 올 수 있는 숫자까지 포함하면서 이 숫자의 합이 9의 배수인 조건도 만족한다.
즉 1로 시작하고 7로 끝나는 9의 배수인 6자리 수에서 이 조합이 나오게 될 것이다. 각 순열을 정수로 변환하고, 이를 2~6배한 각각의 수가 모두 같은 순열인지를 검사한다. 순열 검사는 각 자리 수로 분해한 후 정렬하는 방법을 사용하기 때문에 결국 숫자를 각 자리 숫자의 튜플로 만들거나, 그 역변환을 수행하는 digits(), dump() 함수를 정의하여 사용하였다.
찾는 범위를 극도로 줄였기에 수행시간은 매우 짧다.
from functools import reduce
from collections import Counter
dump = lambda xs: reduce(lambda x, y: x * 10 + y, xs)
digits = lambda n: tuple(map(int, str(n)))
def perm_dups(xs, n):
def helper(acc, cnts, n):
if n == 0:
yield acc
return
for k, v in cnts.items():
yield from helper((*acc, k), {**cnts, k:v-1}, n-1)
yield from helper((), Counter(xs), n)
ds = list(range(10)) * 6
for ds in perm_dups(ds): # 7을 일부러 맨 뒤에 넣음
if ds[0] == 0 or ds[0] > 1 or ds[1] > 6:
continue
n = dump(ds)
if d % 9 > 0:
continue
m = dump(sorted(digits(n)))
if all(m == dump(sorted(digits(n * i))) for i in range(2, 7)):
print(n)
break
# 142857
# CPU Times: total 125 ms