오일러 프로젝트 40 번 문제는 소수점 한자리부터의 숫자가 양의 정수를 차례로 붙여나간 특별한 무리수의 임의의 자리수에 관한 문제이다.
소수점 뒤에 양의 정수를 차례대로 붙여 나가면 아래와 같은 무리수를 만들 수 있습니다. 0.123456789101112131415161718192021… 이 무리수의 소수점 아래 12번째 자리에는 1이 옵니다 ( 붉게 표시된 숫자). 소수점 아래 n번째 숫자를 dn이라고 했을 때, 아래 식의 값은 얼마입니까?
d1 × d10 × d100 × d1,000 × d10,000 × d100,000 × d1,000,000
(http://euler.synap.co.kr/prob_detail.php?id=40)
접근
해당 소수의 임의의 n 자리에 대한 일반항을 세우는 것은 제법 까다로워 보인다. (어찌어찌하면 만들 수 있을 것 같기는 한데) 이런 경우에는 차라리 앞에서부터 매 자리를 만들어서 체크해나가는 것이 쉽겠다. 특히 파이썬의 제너레이터로 해당 수열 생성기를 만드는 것을 별로 어려워보이지 않는다.
- 1 부터 시작한다.
- 이 값을 문자열로 만들고 첫번째 자리부터 리턴하기 시작한다.
- 문자열의 마지막 글자를 리턴했다면, 1로 돌아가서 정수값을 +1 증가시킨다.
이 과정을 무한반복하는 제너레이터를 생성하고, 매 차례를 카운트하면서 1, 10, 100… 번째인 경우만 골라 담아서 곱을 구하면 된다.
제너레이터
def gen(): ## 제너레이터의 경우 몇 번째 항인지의 정보도 같이 리턴하도록 한다.
n, step = 1, 1
while True:
s = str(n)
for c in s:
yield int(c), step
step += 1
n += 1
제너레이터는 생각보다 간단하다. 몇 번째 항을 얻었는지를 제너레이터 외부에서 계산하는 것은 실수의 소지가 있어서 제너레이터가 호출자에게 알려주는 편이 좀 더 편리한 디자인이라고 판단했다. 덕분의 메인 코드는 매우 간단하다.
def e40():
g = gen()
r = 1
for i in range(7):
while True:
x, step = next(g)
if step == 10**i :
r *= x
break
print(r)
%time e40()
# Wall time: 124 ms부록 : Swift 코드
Swift의 경우에는 이런 제너레이터를 만드는 편리한 문법이 아직까지 존재하지는 않는다. (뭐 꼭 있어야 한다는 법도 없고…) 클래스를 만들어도 되는데, 클로저를 이용해서 풀어보도록 하자. (그럼에도 불구하고 중단 위치에서 계속 이어서 수행할 수 있는 파이썬 제너레이터같은 기능이 너무 아쉽다.)
let generate: () -> (Int, Int) = {
var n = 1
var step = 0
var s = String(n)
var pos = s.startIndex
return { () -> (Int, Int) in
let p = Int(String(s[pos]))!
step += 1
pos = s.index(after:pos)
if pos >= s.endIndex {
n += 1
s = String(n)
pos = s.startIndex
}
return (p, step)
}()
main: do {
var r = 1
for i in 0..<7 {
let l = Int(pow(10, Double(i)))
while True {
let (x, step) = generate()
if step == l {
r *= x
break
}
}
}
print(r)
}