[Project Euler 123] (p-1)^n + (p+1)^n % p^2

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

---

p_n 이 n번째 소수 ( 2, 3, 5, 7, 11, ..., )이고, r이 (p_n1)ⁿ + (p_n+1)ⁿ 를 p_n²으로 나눈 나머지라고 하자.

예를 들어, n = 3, p₃ = 5 이고, 4³ + 6³ = 280 5 mod 25 이다.

이 나머지가 10⁹을 넘는 가장 작은 n은 7037이다. 나머지가 10¹⁰을 넘는 가장 작은 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.
        returns 
              n        n       2
         (p-1)  + (p+1)   mod p
        =
                  n-1       n                2
          n p (-1)    + (-1)  + n p + 1 mod p
    '''
    if n%2 == 0:
        fp = 2
    else:
        fp = 2*n*p
    return fp % (p*p)

primes = [ 2, 3, 4, 5, 7, 11, 13, 17, 19, 23 ]

#for i in range(len(primes)):
#   print remainder0(primes[i], i+1) == remainder(primes[i], i+1)

n = 10
candidate = 29
while True:
    IsPrime = False
    for p in primes:
        if p*p > candidate:
#           print candidate
            IsPrime = True
            break
        if candidate%p == 0:
            break
    if IsPrime:
        if remainder(candidate, n) > 10**10:
            print n, candidate
            break
        primes.append(candidate)
        n+=1
    candidate+=1