project euler

프로젝트 오일러 029

2와 100사이의 수들을 밑과 지수로 했을 때, 중복을 제외한 값의 개수

sooop

sooop

— 3 min read
프로젝트 오일러 029
Photo by Sarah Dorweiler / Unsplash

문제

29번 문제
2 ≤ <var>a</var> ≤ 100 이고 2 ≤ <var>b</var> ≤ 100인 <var>a</var>, <var>b</var>로 만들 수 있는 <var>a</var><sup><var>b</var></sup>의 개수
사이냅소프트

너무 쉬움 주의

100의 100승과 같은 큰 수 때문에 한 때 이것은 어려운 문제였을 수 있겠으나, 더 이상은 어렵지 않습니다. 

print(len(set(x**y for x in range(2, 101) for y in range(2,101))))

그다시 설명은 필요치 않아 보입니다.

지수법칙

너무 허무하게 지나갈 수는 없으니, 다른 방법으로도 접근해보겠습니다. 지수로 이루어지는 수들을 튜플의 형식으로 써 보는 겁니다. 예를 들어 87 을 (8, 7) 이라고 쓰는 것입니다. 그런데 8은 2의 세제곱(23)이므로, (23, 7)이고 지수 법칙에 의해 (2, 21)과 같음을 알 수 있습니다. 이런 식으로 밑이 다른 수의 거듭제곱이면 카운트 하지 않는 것이죠.

a, b의 범위는 각각 2∙∙∙100의 범위이기 때문에 검사해야 하는 범위는 한정적입니다. 특히 27 까지만 100보다 작기 때문에, 2~10까지 범위에서 7제곱으로 표현되는지를 검사하거나 로그를 이용해서 계산할 수도 있습니다. 

from math import log

def lower_base(a, b):
    for i in range(2, 11):
        if i >= a:
            break
        j = int(log(a, i))
        if i ** j == a:
            return (i, b * j)
    return (a, b)

xs = set(lower_base(x, y) for x in range(2, 101) for y in range(2,101))
print(len(xs))

큰 수의 지수 계산

큰 수의 곱셉을 이용하면 지수 계산도 할 수 있습니다. 어쩌면 이 문제의 출제 의도는 큰 수의 지수 계산을 사용하라는 것인지도 모르겠습니다. 큰 수의 곱셈 구현도 성능이 썩 나쁘지는 않습니다만, 지수 계산은 다음과 같은 재귀적인 방법으로 횟수를 줄일 수 있습니다. 

def s_pow(x: list[int], y: int) -> list[int]:
    if y == 0:
        return [1]
    if y == 1:
        return x
    w = s_pow(x, y // 2)
    z = s_multi(w, w)

    if y % 2 == 0:
        return z 
    return s_multi(z, x)

Read more