[Project Euler 148] 파스칼 삼각형 mod 7

http://projecteuler.net/index.php?section=problems&id=148

파스칼 삼각형을 7번째 줄까지 써보면, 7로 나누어 떨어지는 것이 없다는 걸 알 수 있다.:

						1
					1		1
				1		2		1
			1		3		3		1
		1		4		6		4		1
	1		5		10		10		5		1
1		6		15		20		15		6		1

그러나, 100번째 줄까지를 보면, 5050개의 숫자 중에서 2361개만 7로 나누어 떨어지지 않는다.

10억(10⁹)번째 줄까지 중에서 7로 나누어 떨어지지 않는 것의 갯수를 구하라.

우선, a+b mod n = (a mod n) + (b mod n) mod n 과 같다는 걸 이용해서 그림을 그려보면, 아주 예쁜 프랙탈모양을 이룸을 알 수 있다. 그리고, 숫자를 7진수로 변환한 후 생각하면 훨씬 생각이 간단해 진다는 걸 알 수 있다. 그러니까, 7까지의 나누어 떨어지지 않는 갯수는 S(n) = n(n+1)/2 로 삼각수이다. 그리고, 7*7까지 n*7 까지 나누어 떨어지지 않는 갯수는, S(7) 모양의 삼각형을 단위로 삼각수 모양을 이룬다. 즉 S(n*7) = S(7)*S(n) 이다. 좀 어려운 7*7 까지 중에서 7로 나누어 떨어지지 않는 m 에 대한 것은, S(m) = S(n*7 + m') = S(7)*S(n) + (n+1)*S(m') 이 된다. 이런 식으로 따져 올라가면서 계산한다. 이걸 파이썬으로 짜봤다. 맑게 생각이 안 되서, 코드가 지져분하다.

#!/usr/bin/env

def dec2sep(n):
    l = []
    while n > 0:
        l.append(n%7)
        n/=7
    return l

limit = 10**9

limit_7 = dec2sep(limit)

print limit_7

whole_triangle = [ 28**i for i in xrange(11) ]
n_tri = [ i*(i+1)/2 for i in xrange(8) ]
sum = 0
remainder = 0
i = 0

for digit in limit_7:
    sum = n_tri[digit]*(28**i) + (digit+1)*remainder
#   print sum, "---"
    remainder = sum
#   print remainder
    i+=1
print sum