Problem 080 : Square root digital expansion (20%)

Description

original

It is well known that if the square root of a natural number is not an integer, then it is irrational. The decimal expansion of such square roots is infinite without any repeating pattern at all.

The square root of two is 1.41421356237309504880…, and the digital sum of the first one hundred decimal digits is 475.

For the first one hundred natural numbers, find the total of the digital sums of the first one hundred decimal digits for all the irrational square roots.

간략해석

100보다 작고 제곱근이 무리수인 수들에 대하여 100자리까지의 합들의 합을 구하여라.

Idea & Algorithm

naive idea

소수점 100자리를 C로 바로 얻기는 힘들다. 부동소수점 방식에 따른 오차는 100자리 이전에 오차를 내기 때문이다.

그렇기에 이 문제의 경우는 실제 빅인티저를 구현하여 이분 탐색으로 계속하며 근사값을 얻어낼 수 있을 것이다.

advanced idea

하지만 100자리까지 나타나는 언어가 있다면 그 언어를 사용하면 된다. Python의 Decimal 모듈을 이용하여 수의 정밀도를 높였다.

제한없는 환경은 이럴 때 가장 큰 효력을 발휘한다.

source code

from decimal import getcontext, Decimal

getcontext().prec = 105 # 정밀도 설정, 이렇게 설정하면 수의 정밀도가 소수점 105자리까지 가능하다.

SZ, d, s = 100, 100, 0 # SZ는 크기, d는 10^99을 곱해줄 수, s는 정답값인 합

p = pow(10, d-1) # 10^99를 곱해주고 그 값을 첫자리부터 100자리까지 더해주면된다.

for i in range(2, SZ):
    q = Decimal(i).sqrt()
    if q % 1 == 0 : # 제곱근이 정수인 경우
        continue
    else :
        s += sum(int(c) for c in str(q * p)[:d])

print (s)

Problem 080