본문 바로가기

프로그래밍/오일러프로젝트

[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^(9))번째 줄까지 중에서 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