책 이야기

서로 다른 소수인 p와 q로 만들어지는 정수 p^qq^p는 합성 정수(Hybrid Integer)라 부른다.

예를 들어, 800=2⁵5²은 합성 정수이다.

C(n)을 n이하의 합성 정수의 갯수라 정의하자.

C(800)=2이고 C(800⁸⁰⁰)=10790이다.

C(800800⁸⁰⁰⁸⁰⁰)을 구하시오.

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

처음에는 숫자가 너무 커서 다루기 겁이 나서 지나갔던 문제이다. 다른 사람의 접근을 보니 숫자가 너무 크기 때문에 log를 이용하면 해결 가능할 것으로 보였다. 문제에서 요구하는 것은 p^qq^p가 800800⁸⁰⁰⁸⁰⁰ 이하인 경우를 묻고 있으므로 다음과 같이 된다. 그리고 양변에 로그를 씌워 다시 정의하면 아래와 같다.

p^qq^p <= 800800⁸⁰⁰⁸⁰⁰

log(p^qq^p) <= log(800800⁸⁰⁰⁸⁰⁰)

log(p^q)+log(q^p) <= log(800800⁸⁰⁰⁸⁰⁰)

q*log(p)+p*log(q) <= 800800*log(800800)

소수는 2부터 시작하므로 800800*log(800800)을 최대값으로 보고 이보다 크게 되는 q*log2+2*log(q)의 q값을 구해 상한선으로 두고 이중 반복문을 운영하면 답을 구할 수 있다. 파이썬의 배열 한계를 넘어갈 것을 걱정했는데, 다행히 천만~2천만 사이의 어딘가에서 최대값을 넘는 것을 확인하고, 정확한 값을 구할 수 있었지만 안전하게 해서 답을 구하기로 했다.

15분쯤 소요되었으니 빠른 것은 아니지만 문제를 해결했다는 것에 만족하기로 했다.

Comparing two numbers written in index form like 2¹¹ and 3⁷ is not difficult, as any calculator would confirm that 2¹¹ = 2048 < 3⁷ = 2187.

However, confirming that 632382⁵¹⁸⁰⁶¹ > 519432⁵²⁵⁸⁰⁶ would be much more difficult, as both numbers contain over three million digits.

Using base_exp.txt (right click and 'Save Link/Target As...'), a 22K text file containing one thousand lines with a base/exponent pair on each line, determine which line number has the greatest numerical value.

NOTE: The first two lines in the file represent the numbers in the example given above.

지수로 표현된 두 수 2¹¹과 3⁷을 비교하는 것은 어렵지 않다. 계산기를 이용하면 2¹¹ = 2048 < 3⁷ = 2187을 확인할 수 있다.

그러나, 3백만 자릿수 이상이 되는 두 수가 632382⁵¹⁸⁰⁶¹ > 519432⁵²⁵⁸⁰⁶ 인 것을 확인하는 것은 상당히 어렵다.

1천 개 이상의 밑과 지수 쌍이 각 행에 있는 22K 크기의 텍스트 파일 base_exp.txt (오른쪽 클릭하고 다른 이름으로 링크 저장) 중 가장 큰 값을 가지는 숫자를 찾으시오.

주의: 파일의 첫 두 줄은 위의 예시에 있는 숫자이다.

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

정직하게 프로그래밍 했더니 역시나 OverflowError: math range error라는 에러메시지를 보게 되었다. 급격하게 커지는 지수를 따라가지 않고 계산할 방법은 이제는 까맣게 잊어버린 log를 다시 찾아보는 방법밖에 없어 보인다.

로그의 지수법칙(loga^b=bloga)을 이용하여 동일한 밑인 상황에서 base_exp 파일의 밑과 지수를 로그에 대입하면(문제의 예시에서 518061*log632382와 525806*log519432를 비교하는 형태) 어렵지 않게 해결 가능하다.