책 이야기

The number, 1406357289, is a 0 to 9 pandigital number because it is made up of each of the digits 0 to 9 in some order, but it also has a rather interesting sub-string divisibility property.

Let d₁ be the 1^st digit, d₂ be the 2^nd digit, and so on. In this way, we note the following:

• d₂d₃d₄=406 is divisible by 2
• d₃d₄d₅=063 is divisible by 3
• d₄d₅d₆=635 is divisible by 5
• d₅d₆d₇=357 is divisible by 7
• d₆d₇d₈=572 is divisible by 11
• d₇d₈d₉=728 is divisible by 13
• d₈d₉d₁₀=289 is divisible by 17

Find the sum of all 0 to 9 pandigital numbers with this property.

1406357289는 0에서 9까지 숫자로 구성되어 있으므로 0에서 9 pandigital 숫자이지만, 다소 재밌는 부분 문자열 속성을 가지고 있다.

The number, 1406357289, is a 0 to 9 pandigital number because it is made up of each of the digits 0 to 9 in some order, but it also has a rather interesting sub-string divisibility property.

d₁을 첫번째 문자, d₂를 2번째 문자 등으로 부르면 다음을 알 수 있다:

• d₂d₃d₄=406은 2로 나눌 수 있음
• d₃d₄d₅=063은 3으로 나눌 수 있음
• d₄d₅d₆=635은 5로 나눌 수 있음
• d₅d₆d₇=357은 7로 나눌 수 있음
• d₆d₇d₈=572은 11로 나눌 수 있음
• d₇d₈d₉=728은 13으로 나눌 수 있음
• d₈d₉d₁₀=289은 17로 나눌 수 있음

이런 속성을 가진 0에서 9 pandigital 숫자의 합계는 얼마인가?

--------------------------------------------------------------------------

32번 문제로 처음 나와 이번에 4번째 나오는 pandigital 관련 문제의 난이도가 계속 올라간다.

반목문을 이용해 10자리 pandigital 숫자를 차례대로 만들고, 숫자를 3개씩 6개로 쪼개어서 각 숫자가 2, 3, 5, 7, 11, 13, 17로 나눠지는지 확인하여 해당하는 숫자의 합계를 구하면 된다.

숫자를 문자열/리스트로 바꾸는 것, 이것을 활용해 숫자의 일부를 잘라내는 것 등이 익숙해져 파이썬으로 답을 구하는 데 그리 어렵지 않았다. 성능 향상을 위해 4번째 숫자가 짝수인지만 확인해도 2로 나눠지는지 검증 가능하고, 6번째 자리고 0,5인지 확인해도 5로 나눠지는지 검증 가능하지만 큰 차이는 없을 것 갈아 다른 숫자와 동일한 형태로 3자리 숫자를 잘라내어 검증하는 형태로 구성했었다.

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once. For example, 2143 is a 4-digit pandigital and is also prime.

What is the largest n-digit pandigital prime that exists?

1부터 n까지 한번씩 모든 숫자를 사용하여 만들어진 n자리 숫자를 pandigital이라 부른다. 예를 들어, 2143은 4자리 pandigital이며 또한 소수이다.

가장 큰 n자리 pandigital 소수는 무엇인가?

--------------------------------------------------------------------------

답을 구하는 기본 원리는 간단하다. 각 자리 숫자에 대한 pandigital을 구하고 소수인지 확인하여 가장 큰 값을 찾으면 되는 것이다. 실제 그렇게 구현했고, 시간도 많이 걸리지 않아 다음 문제로 넘어갔던 것 같은데, 이 글을 쓰면서 생각해보니 효율을 높일 방법이 여러가지가 있어 보인다.

우선, 작은 숫자부터 올라가면 모든 조합을 확인해야 가장 큰 pandigital 소수를 찾을 수 있지만, 큰 숫자부터 내려오면서 pandigital을 검증하면 가장 먼저 찾는 소수가 가장 큰 pandigital 소수가 된다. 그리고, 1~9의 합이 3의 배수이기 때문에 9자리는 모든 숫자가 3으로 나눠지므로 소수가 아니고, 1~8의 합도 마찬가지로 3의 배수이기 때문에 8자리 숫자도 검증할 필요가 없다. 즉, 7자리 숫자의 가장 큰 pandigital에서 시작하여 내려오면서 가장 먼저 나오는 소수가 해답이 되므로, 훨씬 빠른 시간에 답을 구할 수 있을 것이다.

Take the number 192 and multiply it by each of 1, 2, and 3:

    192 × 1 = 192
    192 × 2 = 384
    192 × 3 = 576

By concatenating each product we get the 1 to 9 pandigital, 192384576. We will call 192384576 the concatenated product of 192 and (1,2,3)

The same can be achieved by starting with 9 and multiplying by 1, 2, 3, 4, and 5, giving the pandigital, 918273645, which is the concatenated product of 9 and (1,2,3,4,5).

What is the largest 1 to 9 pandigital 9-digit number that can be formed as the concatenated product of an integer with (1,2, ... , n) where n > 1?

192를 1, 2, 3으로 곱하면 다음과 같다:

    192 × 1 = 192
    192 × 2 = 384
    192 × 3 = 576

각 결과물을 연결시켜 보면 1에서 9 pandigital인 192384576을 구할 수 있다. 192384576을 192와 (1, 2, 3)의 연결된 곱(concatenated product)으로 부른다.

9를 1, 2, 3, 4, 5로 곱해서 연결하면 1에서 9 pandigital인 918273645가 되며, 이것은 9와 (1, 2, 3, 4, 5)의 연결된 곱이다.

1보다 큰 자연수(1, 2, ..., n)으로 만들 수 있는 연결된 곱 중 가장 큰 9자리의 1에서 9 pandigital은 무엇인가?

--------------------------------------------------------------------------

문제에서 n을 2 이상으로 한정했기 때문에 5자리 숫자는 최소 10자리가 되어서 1에서 4자리 숫자의 범위 내에서 찾으면 되는 것을 알 수 있다.

숫자에 1, 2, 3 등을 차례로 곱하면서 나온 결과물을 연결한 길이가 9인 경우(10 이상이면 다음 숫자로), 9자리 숫자에 1~9까지 숫자가 하나씩 있는지 확인하는 것을 반복하면 된다.  결과로 나온 값을 정렬해서 가장 큰 수를 구하면 되기 때문에 보기 보다는 어렵지 않게 해결할 수 있다.

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once; for example, the 5-digit number, 15234, is 1 through 5 pandigital.

The product 7254 is unusual, as the identity, 39 × 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital.

Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.

HINT: Some products can be obtained in more than one way so be sure to only include it once in your sum.

1부터 n까지 숫자가 각 자리에 한 번씩 사용되었으면 그 n자리 숫자를 pandigital이라 부른다. 예를 들어, 5자리 숫자 15234는 1에서 5 pandigital이다.

7254는 39x186=7254로 승수, 피승수, 곱이 1에서 9 pandigital이므로 특이하다.

승수/피승수/곱이 1에서 9 pandigital인 숫자의 곱의 합을 구하시오.

힌트: 어떤 곱은 한 가지 이상의 방법으로 구할 수 있는데 합계에서 한 번만 포함되어야 한다.

--------------------------------------------------------------------------

pandigital이라는 단어는 처음 보는데 검색해봐도 한글로 대응되는 단어가 나오지 않았다.

간단히 생각하면 1~98765432까지 승수와 피승수를 이중으로 반복하면서 곱을 구해서 승수, 피승수, 곱이 1에서 9 pandigital인지 판정하고, 곱의 중복을 제거하여 더하면 된다. 하지만, 불필요한 계산이 많이 포함되어 시간이 엄청 오래 걸리므로 좀 더 빠른 속도로 구할 수 있는 개선방안이 필요하였다.

'승수x피승수=곱' 관계에서 예시는 2자리x3자리=4자리인 경우이다. (3자리x2자리=4자리와 같이 동일한 결과가 나올 경우를 제외하고) 이 외에 가능한 경우를 생각해 보면, 1자리x4자리=4자리 밖에 없다.

승수가 1자리이고 피승수가 4자리인 반복문과 승수가 2자리이고 피승수가 3자리인 반복문에서 pandigital 숫자 여부를 판정하고, 결과를 집합으로 변형하여 중복을 제거하고 합계를 구하였다.

pandigital 숫자 여부를 판정하는 것은 승수/피승수/곱의 자리수를 확인하고 합집합을 만들어서 1~9가 있는 집합과 동일한지 비교하거나, 1~9가 있는 집합에서 승수, 피승수, 곱의 차집합을 차례로 구해서 null이 되는지 확인하는 등 개인 성향에 따라 여러가지 방법이 가능할 것이다.