콘텐츠로 건너뛰기
Home » 오일러 프로젝트 40

오일러 프로젝트 40

소수점 뒤에 양의 정수를 차례대로 붙여 나가면 아래와 같은 무리수를 만들 수 있습니다. 0.123456789101112131415161718192021…. 이 무리수의 소수점 아래 12번째 자리에는 1이 옵니다. 소수점 아래 n번째 숫자를 dn이라고 했을 때, 아래 식의 값은 얼마입니까?

d1 x d10 x d100 x d1,000 x d10,000 x d100,000 x d1,000,000

http://euler.synap.co.kr/prob_detail.php?id=40

접근

문제에서 제시한 소수를 계속 써나가는 규칙은 간단하지만 n번째 숫자를 찾는 방식은 간단하지 않다. 따라서 일반항이 되는 숫자를 바로 구하지 않고 숫자를 하나씩 수집하도록 한다. 이런 건 제너레이터를 이용하면 정말 수월하다.

def gen():
  idx, n = 1, 1
  while True:
    s = str(n)
    for c in s:
      yield idx, int(c)
      idx += 1
    n += 1

for i, x in gen():
  print(i, x)
  if i > 99:
    break

문제에서 찾기를 요구하는 항은 순서대로 10k (k = 0, 1, 2, 3, 4, 5, 6)에 해당하는 값이므로, 제너레이터가 만들어내는 값 중 순번이 일치하는 것만 골라서 곱해주면 끝.

%%time
res, g, step, d = 1, gen(), 0, 0
for k in range(7):
  while step < 10**k:
    step, d = next(g)
  res *= d
print(res)

더 빠른 방법

제너레이터를 이용해서 백만번의 루프를 도는 것보다 더 빠르게 문제를 해결할 수 있는 방법을 찾아보자. 앞서 말한대로 이 수열의 일반항을 바로 찾아내는 것은 간단치 않다. 하지만 숫자를 하나씩 리턴하기 보다는 10**p 번째 (p = 1, 2, 3,…) 숫자를 구하기 위해서는 1부터 증가하는 n의 자리수를 세어서 누적된 자리수가 10**p를 초과하는 시점에서 해당 순번의 글자를 리턴하도록 할 수는 있다.

def gen() -> Generator[tuple[int, int], None, None]:
  step, idx, n = 0, 1, 1
  while True:
    m = str(n)
    if idx + len(m) > 10**step:
      yield (10**step, int(m[10**step - idx]))
      step += 1
    idx, n = idx + len(m), n + 1

res, g = 1, gen()
for _ in range(7):
  _, v = next(g)
  res *= v
print(res)

백만번째 숫자까지만 검사했을 때에는 약 다섯 배 정도 빠르게 작동하는데, 만약 조사하고자하는 숫자의 위치가 훨씬 더 크다면 이 방법이 더 유리할 것이다.