생성함수
수열을 점화식으로 표현할 수도 있지만, 생성함수(generating function)라는 다항식을 이용해서 표현하는 방법도 있다고 한다. 뭔가 싶었다. 그런데, 좀 생각을 해 보니, 소수표현과 분수에 비유해서 설명할 수 있지 않을까 하는 생각이 들었다. 그러니까, 3/7 이라는 소수는 0부터 9까지의 수만 갖는 무한수열을 표현한다. 0.428571428571... 을 4, 2, 8, 5, 7, 1... 이렇게 이어지는 무한수열을 나타내는 것이라고 보자는 거다. 그럼, 좀 복잡한 점화식 대신에, 3/7 이라는 간단한 수로 무한한 수열을 표현할 수 있다. 그런데, 정수의 소수표현은 0부터 9까지의 수만 수열의 한 항으로 가질 수 있다는 한계가 있다. 이건 진법을 바꾸면 무한하게 늘어날 수 있겠지만, 아무리 ..
[Project Euler 204] 해밍수
해밍수(Hamming number)란 5보다 큰 소수 인수를 갖지 않는 양수를 말한다. 즉, 해밍수를 작은 것부터 몇 개 나열하면 다음과 같다. 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15. 108보다 작은 해밍수는 1105개가 있다. 이 개념을 일반화하자. 타잎 n의 일반화된 해밍수를 n보다 큰 소수 인수를 갖지 않는 양수로 정의하자. 즉, 해밍수는 타잎 5의 일반화된 해밍수가 된다. 109보다 작은 타잎 100의 일반화된 해밍수는 몇 개 인가? 재귀로 풀었다. 아래가 코드. #!/usr/bin/env python # Euler Project Problem 204 # Hamming number import math LIM = 10**8 count = 0 for a in range(in..
[Project Euler 123] (p-1)^n + (p+1)^n % p^2
http://projecteuler.net/index.php?section=problems&id=123 pn 이 n번째 소수 ( 2, 3, 5, 7, 11, ..., )이고, r이 (pn1)n + (pn+1)n 를 pn2으로 나눈 나머지라고 하자. 예를 들어, n = 3, p3 = 5 이고, 43 + 63 = 280 5 mod 25 이다. 이 나머지가 109을 넘는 가장 작은 n은 7037이다. 나머지가 1010을 넘는 가장 작은 n을 구하라. #!/usr/bin/env python # Project Euler Problem 123 def remainder0(p, n): return ((p-1)**n + (p+1)**n)%(p*p) def remainder(p, n): ''' p is a prime. r..
