[Project Euler] 52. Permuted multiples

1. 개요

    문제는 이곳에서 확인할 수 있다. $(x)$를 양의 정수 $x$의 각 자리의 숫자라고 하자. $(x)=(2x)$가 성립하는 $x$ 중의 하나는 125874가 있다. $(x)=(2x)=(3x)=(4x)=(5x)=(6x)$가 성립하는 최소 $x$를 찾는 것이 문제의 목표이다.  

2. 구현

    문제의 특성을 잘 살펴보면 확인해야 할 숫자를 많이 줄일 수 있다. 먼저 $(x)$ = $(6x)$이므로 $x$는 반드시 1로 시작한다. 그렇지 않으면 자리수가 달리지기 때문이다. 또한 $5x$가 5의 배수이므로 마지막 수는 0 또는 5이다. 따라서 $(x)$는 0 또는 5를 포함한다. 마찬가지로 $2x$가 2의 배수이므로 $(x)$는 0, 2, 4, 6 또는 8을 포함한다. 또한 $x$는 3의 배수이다. 왜냐하면 $(3x)$의 합이 3의 배수이며 $(x)=(3x)$이기 때문이다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

# -*- coding: utf-8 -*-   i = 1   while True:       # 3x가 3의 배수이고 x와 3x의 digit이 같으므로 x도 3의 배수이다.     x = 3*i     x_digit = sorted(list(map(int, str(x))))       # 6x와 x의 digit이 같으므로 x는 1로 시작한다.     # 5x가 5의 배수이므로 x는 0 또는 5를 포함한다.     # 2x가 2의 배수이므로 x는 0, 2, 4, 6 또는 8을 9포함한다.     if x_digit[0] != 1 or not any(d in [0, 5] for d in x_digit) or not any(d in [0, 2, 4, 6, 8] for d in x_digit):         i += 1         continue       result = True       for k in range(2, 7):         result &= x_digit == sorted(list(map(int, str(k*x))))       if result:         print(x)         break       i += 1

    답은 142857이다.