프로젝트 오일러 052
2배, 3배, 4배, 5배, 6배를 하여도 같은 숫자로 이루어지는 가장 작은 수
문제
사이냅소프트
50번까지는 몸풀기였습니다. 이제 당분간은 제법 빡세다고 느껴지는 문제들을 자주 만나게 됩니다.
순열인 수들
123, 321, 213 과 같이 같은 숫자들이 순서만 다르게 조합되어 있는 수들은 마치 1, 2, 3으로 만들 수 있는 순열과 같습니다. 실제로 이렇게 부르는 지는 잘 모르겠습니다만, 편의상 이러한 수들을 '순열인 수들'이라고 칭하겠습니다.
순열인 두 수에서 서로 다른 위치에 있는 같은 숫자들이 나타내는 값의 차는 얼마일까요? 321과 132의 경우를 살펴봅시다.
- 3 -> 300 - 30 = 270 = 3 × (100 - 10)
- 2 -> 20 - 2 = 18 = 2 × (10 - 1)
- 1 -> 100 - 1 = 99 = 1 × (100 - 1)
모두 원래의 숫자 x (10a - 10b)의 모양을 하고 있고, 10의 거듭제곱 끼리의 차는 9의 배수이므로, 이 모든 차이의 합 역시 9의 배수가 됩니다.
어떤 수 N과 그 수를 두 배 한 2N의 차는 원래의 수인 N입니다. 그런데, N과 2N은 순열인 수가 된다면 N이 9의 배수여야 합니다.
제약 조건
그 외의 제약조건들을 찾아봅시다. 우선 몇 자리 수에서 우리가 찾는 답이 나올 수 있을까요? (사실 이 조건이 문제를 푸는 시간과 제일 밀접하게 관련이 있을 거에요. 루프를 돌아야 하는 범위를 결정하거든요)
일단 좀 쉬운 힌트부터 생각해봅시다. 일단 어떤 수 N은 6배 할 때까지 자리수가 변하지 않습니다. 그러려면 앞의 두 숫자는 정해져야 합니다. 12···, 13···, 14···, 15···, 16··· 정도가 되겠네요. 17 × 7 = 119라서 자리수가 바뀝니다. 그리고 11은 22, 33, 44, 55, 66을 만들기 때문에 순열을 찾으려면 아주 많은 자리수가 필요할 것으로 보이니 제외할 수 있습니다. 따라서 1은 반드시 숫자에 포함되며, 2, 4, 5, 6 중 하나가 두 번째 자리에 올 수 있습니다.
뒷자리는 어떨가요? 역시 배수를 생각할 때 너무 많은 숫자가 나오면 곤란합니다.
- 끝자리가 2라면 배수의 끝자리는 4, 6, 8, 9, 0 이 등장합니다. 곱셈할 때 올림이 발생하면 이 숫자들 외에 홀수도 필요합니다. 따라서 끝자리가 2가 될 가능성은 아주 낮습니다.
- 끝자리가 3이라면 배수의 끝자리는 6, 9, 2, 5, 8이 나옵니다. 앞자리에는 1이 와야 하므로 최소 7개의 숫자가 필요합니다.
- 끝자리가 5라면 배수의 끝자리는 5, 0이 반복됩니다. 첫자리 수가 증가할 것을 생각하면 1, 2, 4, 7, 8까지 필요합니다. 필요한 숫자는 7개가 됩니다.
- 끝자리가 7이라면 7, 4, 1, 8, 5, 2로 6개가 됩니다. 그리고 이 6개는 그 합이 9의 배수이며, 여기에 앞자리 숫자 구현에 필요한 값들도 모두 포함되어 있습니다. 즉 1****7이고, 이 사이에는 2, 4, 5, 8 의 순열이 채워지는 값이라면 가능성이 있습니다!
즉 6자리이며, 양끝은 1과 7인 6자리 숫자 내부에 중복을 포함하는 순열로 숫자 4개를 채우고 이 조건을 검사합니다.
같은 순열인지 체크는 각 숫자를 분해해서 정렬한 튜플이 동일한지를 검사하였습니다. 위의 고민을 통해서 범위를 아주 크게 줄였기 때문에 수행 시간은 매우 짧습니다.
from euler import permutations_dup
def main():
digits = lambda n: tuple(map(int, str(n)))
ds = list(range(10)) * 5
for ds in permutations_dup(ds, 4):
if ds[0] > 6:
continue
ds = (1, *ds, 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
if __name__ == '__main__':
main()
