Wireframe

오일러 프로젝트 80

sooopd

80번 문제는 자연수의 제곱근을 100자리까지 구하는 문제이다. 대부분의 프로그래밍 언어들은 실수의 제곱근을 계산하는 함수를 제공하지만, 기본 실수타입은 100자리까지의 정밀도를 제공하지 않는다. 따라서 손으로 제곱근을 구하는 계산과정을 코드로 구현해야 한다.

문제

자연수의 제곱근이 정수가 아니라면 무리수가 되고, 이런 경우 소수점 밑으로 반복되는 패턴이 전혀 없는 숫자들이 무한히 전개됩니다.

2의 제곱근은 1.41421356237309504880… 인데, 처음 100개까지의 자릿수를 모두 더하면 475입니다.

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

제곱근 계산하기

이는 중학교과과정에서 배우는 제곱근 계산하는 방법을 사용한다. 이 방법은 실제 손으로 계산하기에는 많은 노력을 요구하지만, 인내심만 있다면 원하는 만큼의 정밀도까지 계산해 나갈 수 있다.  손으로 제곱근을 구하는 방법은 ‘수학이야기’ 블로그를 참고하자. 아래 그림은 해당 블로그에서 가져온 내용이다.

이 손 계산을 따라가는 로직을 만들어 보자. 먼저 왼쪽부터 쌓아 내려가는 값이 있다. 이 값을 A 라고 하자. A의 초기값은 0 이다.

그리고 오른쪽에서 점차 빠지면서 내려오는 값이 있다. 이 값을 B라고 하자. B는 A를 이용해서 만들어지는 어떤 수를 뺀 다음, 다시 “00”을 붙여서 다음 값을 만든다.

A를 계산에 적용하기 위해서는 A 뒤에 숫자 C를 붙인다. 이 값을 C와 곱해서 B에서 빼야하는데, 이 때 C는 'AC' * C 한 값이 B를 넘지 않는 범위에서 정해야 한다.  이 관계를 다시 정리하면 다음과 같다.

제곱근의 해는 매 C항의 값을 연결해나가면 된다. 참고로 여기서 N의 범위는 100미만이기 때문에 모든 제곱근값의 정수부는 한자리가 될 것이다.

제곱근 구하기 구현

제곱근 구하기 함수는 다음과 같이 정리될 수 있겠다. 

def sqrt(n, count=20):
  '''100미만의 정수 N의 제곱근을 숫자 count개까지 구한다.'''
  result = []
  a, b, c = 0, n, 0
  while c < count and b > 0:
    ''' 일의 자리가 될 숫자 i 찾기'''
    for i in range(1, 11):
      if (a * 10 + i) * i <= b:
        continue
      break
    # i 가 허용치를 넘었을 때 루프가 끝나므로
    i = i - 1
    result.append(i)
    b = (b - (a * 10 + i) * i) * 100
    a = (a * 10 + i) + i
    c += 1
  return result

이 함수를 이용해서 2의 제곱근을 100자리까지 찾아서 자리수의 합을 계산해보자.

>>> print(sum(sqrt(2, 100)))
475

최종 정답은 다음과 같이 구한다. 제곱근이 무리수가 아닌 경우는 완전 제곱수로, 이들의 sqrt() 결과는 원소 1개짜리 리스트가 될 것이다. 다음과 같이 전체 집합을 구해서 합산한다.

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

참고

이 문제에서 사용된 sqrt() 함수는 100미만의 자연수의 제곱근을 계산하는데에만 쓰일 수 있다. 100보다 큰 자연수의 제곱근을 구할 수 있는 방법이 있을까? 예를 들어 131의 제곱근을 구하기 위해서는 1부터 시작하고 31, 00, 00, …. 이 내려오는 식으로 계산을 수행해나가야 한다. 이 구현에 대해서는 다음에 시간이 날 때 다시 다뤄보도록 하겠다.

Exit mobile version