Wireframe

오일러 프로젝트 80

자연수의 제곱근이 정수가 아니라면 무리수가 되고, 이런 경우 소수점 밑으로 반복되는 패턴이 전혀 없는 숫자들이 무한히 전개됩니다.
2의 제곱근은 1.41421356237309504880… 인데, 처음 100개까지의 자릿수를 모두 더하면 475입니다.

1부터 100까지의 자연수 중에서 제곱근이 무리수인 경우에 대해, 처음 100개까지의 자릿수를 더한 값들의 총합은 얼마입니까?

접근

파이썬에서 제곱근을 구하는 방법은 math.sqrt() 함수를 사용할 수도 있고, n ** 0.5를 사용하는 방법이 있다. 그런데 이 두 경우에 연산 결과는 float 타입으로 정밀도가 제한된 부동소수점 숫자 타입을 사용하기 때문에 소수점 아래 99자리까지의 실제 숫자를 알 수 없다. 따라서 임의의 정밀도를 지원하는 타입을 사용하거나, 큰 숫자를 문자열을 통해 덧셈/곱셈했던 것처럼 직접 계산하는 방법을 구현해야 한다.

제곱근을 손으로 구하는 방법

제곱근을 계산하는 방법에는 여러 가지가 있는데, 우리나라 교과과정에서 배우는 방법을 ‘개평법’이라고 한다. 개평법은 다항식의 완전제곱을 원래의 수와 비교하여 맞춰 나가는 방식으로 큰 종이만 있다면 원하는 자리수까지 계산할 수 있다. 개평법의 자세한 원리나 절차는 ‘제곱근 계산법’을 검색해보도록 하자.

제곱근 구하기 구현

위 그림에서 설명하는 제곱근 계산법을 코드로 표현하면 아래와 같다. 완전제곱수처럼 특정한 자리에서 딱 떨어지거나, 계산한 숫자가 미리 정해놓은 상한에 도달할 때까지 계산하고, 계산된 숫자의 리스트에 소수점을 추가하여 문자열로 리턴한다.

def sqrt(n, cnt=100):
    '''100미만의 정수 N의 제곱근을 숫자 count개까지 구한다.'''
    res = []
    a, b, c = n, 0, 0
    while c < cnt and a > 0:
        # 현재 자리의 숫자값 찾기
        x = max(filter(lambda x: (b * 10 + x) * (x) <= a, range(11)))  # 100을 계산하려면 10도 테스트해야한다.
        a = (a - (b * 10 + x) * x) * 100
        b = (b * 10 + x * 2)
        c += 1
        res.append(x)
    return res

print(''.join(map(str, sqrt(3)))
# 1732050807568877293527446341505872366942805253810380628055806979451933016908800037081146186757248575

# 실제 계산 결과와 비교
print(''.join(map(str, sqrt(3, 17))))
# 17320508075688772
print(3 ** .5)
# 1.7320508075688772


위 예제에서는 3의 제곱근을 계산하였는데, 여기서는 우연히 계산 결과와 동일하지만, 오히려 실제 계산 결과(3 ** 0.5)는 근사값이기 때문에 맨 끝자리에서 차이가 날 수 있다.

이 함수를 사용해서 1부터 100까지의 정수의 제곱근을 구한 후, 그 결과가 무리수인 것의 각 자리수의 합의 누적합을 구하면 된다. 자연수중 완전제곱수가 아닌 것들의 제곱근은 모두 무리수이므로 sqrt() 의 결과의 길이가 1보다 큰 것이 모두 대상이 된다.

xs = [sqrt(x + 1) for x in range(100)]
print(sum(sum(x) for x in xs if len(x) > 1))

임의 정밀도의 실수 계산을 위한 Decimal 타입

파이썬은 큰 정수를 지원하여 8바이트 정수범위보다 더 큰 값의 계산도 수행할 수 있지만, float 타입은 64비트로 크기가 고정되어 있어 정확도에 한계가 있다. decimal.Decimal 타입은 필요한 만큼의 유효숫자에 대해 정밀하게 계산을 수행할 수 있는 실수 타입으로, 이 문제의 풀이에 사용될 수 있다. Decimal 타입은 여전히 근사값이므로, 100자리까지의 정확한 숫자를 이용하기 위해서는 101개의 유효숫자를 사용할 수 있도록 지정해야 한다.

from decimal import Decimal, getcontext

getcontext().prec = 101

print(Decimal(2).sqrt().to_eng_string())
# '1.4142135623730950488016887242096980785696718753769480731766797379907324784621070388503875343276415727'

# 2의 제곱근의 100개 유효숫자의 합
sum(map(int, filter(lambda z: z.isdigit(), 
                    Decimal(2).sqrt().to_eng_string()[:101])))
# 475


# 1~100 까지 무리수인 제곱근의 모둔 유효숫자의 합

def process(n):
  return [int(c) for c in Decimal(n).sqrt().to_eng_string()[:101] if c.isdigit()]

sum(sum(process(x + 1)) for x in range(100) if len(process(x + 1) > 2)


Exit mobile version