책 이야기

양의 정수 a,b,c,d가 ab=cd=N이고 a+b=c+d+1인 경우, 양의 정수 N은 은밀하다고(stealthy) 한다.

예를 들어, 36=4x9=6x6은 은밀하다.

10⁶ 이하에는 2851개의 은밀한 숫자(Stealthy Numbers)가 있다.

10¹⁴ 이하에는 몇 개의 은밀한 숫자가 있는가?

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

문제는 그리 까다롭지 않아, 문제에서 요구한 것만 구현하면 코드가 그리 길지 않다. 숫자의 약수를 구해서, 약수가 n개인 경우 n/2개까지 두 숫자를 각각 a, c로 두고, b, d를 연산을 통해 구하고, a+b=c+d+1인 경우를 찾도록 만들었다.

하지만, 예시로 나온 1백만 이하에 몇 개가 있는지 검증하는데 벌써 속도 문제를 만나게 되었다. 문제에서 요구한대로 했을때 구해지는 답을 보고 4의 배수만 나오기 때문에 그것으로 성능을 조금 개선했다. 그래도, 약수를 구하는 부분에서 시간이 많이 소요되어서, 대상 숫자를 보니 전체 약수의 가운데 부근에 있었다. 예를 들어 설명하면 약수가 10개인 경우 4,5번째 숫자 또는 3,4번째 숫자가 a,c가 되는 것이었다. 그렇게 해서 속도를 개선하니 1백만 개 이하의 은밀한 숫자 갯수를 맞게 구할 수 있어서 문제에서 요구한 대로 구현했음을 알 수 있었다.

하지만, 1백만 개에 9초의 시간이 필요했으면, 문제에서 요구한 1경 개를 대상으로 구하려면 적어도 900000000초(250000시간)의 시간이 필요한 상황임을 알 수 있었다. 그 말은 문제를 있는 대로 구현하는 것이 아니고 새로운 알고리즘을 찾는 것을 요구하는 정수론 문제라는 것이었다.

인터넷을 검색해 보니, 깃헙에 누군가가 구현한 내용에서 bipronics라는 명칭으로 x*(x+1)*y*(y+1)을 구하는 정수 배열을 활용해서 구했다고 설명했는데, 그 정수 배열이 문제에서 요구하는 답과 동일한 것이었다. 왜 약수 중에 a+b=c+d+1인 약수와 x*(x+1)*y*(y+1)이 동일한지 이해는 안되었지만 그렇다고 한다. 처음 접근한 방법으로 안되었을 때, 숫자 리스트를 만들고 a+b=c+d+1을 만족하는 경우에 flag을 바꾸는 형태로 해결할 수 있을지 고민하다가, 변수가 너무 많아 포기했는데 조금은 비슷한 접근인 것 같기도 했다.

이 개념으로 구현하니 1백만 개는 0.04초만에 구할 수 있었는데, 그래도 1경 개를 구하는 데에는 시간이 꽤나 걸렸다. 조건에 맞는 리스트를 구하는 것보다 중복을 제거하는 데 시간이 더 많이 걸린 것이 함정이었다. 파이썬의 list(set())의 조합으로 중복을 제거했는데, 7천만 개 이상 리스트에서 중복 제거하는 데 많은 시간을 필요로 했다. 대충 1분 이내에 조건에 맞는 리스트를 구했는데 거기에서 중복을 제거하는 데 10분 이상 소요되었다.

적어도 2개의 소수를 약수로 가지고 있는 수를 합성수라 한다. 예를 들어, 15=3x5, 9=3x3, 12=2x2x3이다.

(서로 다를 필요가 없는) 2개의 소수로 구성된 합성수는 30이하에 10개가 있다:

4, 6, 9, 10, 14, 15, 21, 22, 25, 26

10⁸보다 작은 n에 대해, (서로 다를 필요가 없는) 2개의 소수로 구성된 합성수는 몇 개인가?

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

1억 이하의 숫자 중에 2개 이상의 소수의 곱으로 구성된 합성수가 몇 개인지 묻는 문제이다. 문제에서 (서로 다를 필요가 없는)으로 설명된 부분은 동일한 소수로 곱해도 된다는 뜻이므로, 예시와 같이 9=3x3을 허용하게 구현하면 된다.

빠른 계산을 위해서 1억 이하의 소수 목록을 구하고, 2중 반복문에서 소수끼리 서로 곱하게 해서 목록을 구하고, 파이썬의 집합을 이용해서 중복을 제거해서 구했다. 1억 이하의 소수가 5백만 개 이상 나오더니 목록을 구하면서 메모리 에러가 발생했다. 생각보다 리스트가 커져서 문제가 생긴 것 같았다.

그래서, 결과값 리스트를 만들지 않고, 생성되는 합성수의 갯수를 구하도록 바꿔서 답을 구할 수 있었다. 소수 2개의 곱을 구하는 것이어서 다른 약수가 있을 수 없기 때문에 중복을 제거하는 과정이 필요없었다.

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이 되는지 확인하는 등 개인 성향에 따라 여러가지 방법이 가능할 것이다.