Tag Archives: pell

Euler Problem 66

This one has been sticking out like a sore thumb for a while. I couldn’t figure it out for a long while until I found an algorithm for solving Pell numbers. I also used my old favourite prime number sieve. So I can’t really explain why this works. It just does. Better not question it and go on the next one.

#Euler66
from math import sqrt
class Algorithms:
    def pell(self, d):
        p, k, x1, y, sd = 1, 1, 1, 0, sqrt(d)
        while k != 1 or y == 0:
            p = k * (p/k+1) - p
            p = p - int((p - sd)/k) * k
            x = (p*x1 + d*y) / abs(k)
            y = (p*y + x1) / abs(k)
            k = (p*p - d) / k
            x1 = x
        return x
    def primeGen (self, lowerLimit, upperLimit):
        isPrime = [False, True]
        i = 2
        while i < upperLimit:
            isPrime.append(True)
            i += 1
        p = 2
        while p * p < upperLimit:
            if isPrime[p] == True:
                m = p * p
                while m < upperLimit:
                    if m % p == 0:
                        isPrime[m] = False
                    m += p
            p += 1
        P = []
        count = 0
        for p in isPrime:
            if p and count >= lowerLimit :
                P.append(count)
            count += 1
        return P
class Problem66:
    def __init__(self, limit):
        self.limit = limit
        self.Euler = Algorithms()
    def Solution(self):
        P = []
        for p in self.Euler.primeGen(2,self.limit):
            Pell = self.Euler.pell(p)
            print Pell, p
            P.append((Pell, p))
        return "Answer = "+str(max(P)[1])
if __name__ == '__main__':
    P = Problem66(1000)
    print P.Solution()