Project Euler #381: (prime-k) factorial
문제를 볼까?
For a prime p let S(p) = (∑(p-k)!) mod(p) for 1 ≤ k ≤ 5.
For example, if p=7,
(7-1)! + (7-2)! + (7-3)! + (7-4)! + (7-5)! = 6! + 5! + 4! + 3! + 2! = 720+120+24+6+2 = 872.
As 872 mod(7) = 4, S(7) = 4.It can be verified that ∑S(p) = 480 for 5 ≤ p < 100.
Find ∑S(p) for 5 ≤ p < 108.
소수 p에 대해서 S(p) = (∑(p-k)!) mod(p) (1 ≤ k ≤ 5)라 정의하자. 예를 들자면 p가 7일 때 (7-1)! + (7-2)! + (7-3)! + (7-4)! + (7-5)! = 6! + 5! + 4! + 3! + 2! = 720+120+24+6+2 = 872, 이때 872 mod(7) = 4이니까 S(7) = 4이다. (여기서 m mod n은 m을 n으로 나눴을 때 생기는 나머지를 뜻합니다.) 그러면 p가 5이상 100미만일 때 ∑S(p) = 480임을 확인할 수 있다.
p가 5이상 1억 미만의 소수까지 변할 때를 구하라.
음 이문제는 wilson의 정리를 알면 쉽게 풀립니다.
Wilson's Theorem
p가 소수일 때,
(https://namu.wiki/w/%EC%9C%8C%EC%8A%A8%EC%9D%98%20%EC%A0%95%EB%A6%AC: proof)
그래서 이걸 이용해서 S(p)와 p에 대해 합동인 수를 알아보겠습니다. (p와 합동이라는 말은 p로 나눴을 때 나머지가 같다는 걸 의미합니다.)
일단 
입니다. 그런데 프로그래밍을 할 때 (p-5)!를 직접 계산하라곤 할 수 없으니 (p가 과연 9천만 근처라면?) 주어진 이 수랑 합동인, (p-5)!보단 작은 수를 구해봅시다.
여기서, 제가 차안에서 이동중에 문득 떠올라낸 생각 하나 써보죠.
Claim 1
5이상의 소수 p에 대해서
가 성립한다.
증명은...(p-1)!을 늘리고 늘리다 보면 24(p-5)!랑 mod p에서 합동일텐데, 합동식 좌우변에 (p^2-1)/24를 곱해주면 성립합니다. 아 이때 (p^2-1)/24는 정수입니다. 해보시면 알텐데 p^2는 8로 나눈 나머지가 항상 1이고, 3으로 나눈 나머지도 항상 1이라.. 그리고 x에서 24씩 늘려도 p가 더해지는거라 p대신 mod 24에서 합동인 x를 써도 관계없습니다.
그리고 이제 MATLAB으로 코드를 짰습니다.
그러면....답이 나옵니다. 1.3초 정도 걸리네요. MATLAB은 소수 list 뽑아내는 게 built in function으로 있고, vector 계산이 편해서 이런 류의 문제들 풀기엔 좋은거 같아요. 동시에 빨리 계산할 수 있고..
+다행이도 온라인에서도 MATLAB을 구현할 수 있는 사이트를 알아냈습니다...! 실행제한시간은 10초정도지만 ㅎㅎㅎ (http://octave-online.net/)