## Pell’s equation

Most of you are familier of pell’s equation .I found couple of question related to this problem and finally rewrote it in python as c code was not very much understandable.There are some good discussion about solving pells equation.If you want to solve the problems refer to these sites having very well organised theory about pells equation http://en.wikipedia.org/wiki/Pell’s_equation http://mathworld.wolfram.com/PellEquation.html . I came across this problem on project euler in many variants. This problem use the continued fraction theory.Python code for pell’s equation.

# To change this template, choose Tools | Templates # and open the template in the editor. import math if __name__ == "__main__": while(True): D=int(raw_input()) if(D==0):break L,a_0,p_0,q_0=[],int(math.sqrt(D)),0,1 L.append(a_0) while(True): p_1=a_0*q_0-p_0 q_1=(D-p_1**2)//q_0 a_1=(L[0]+p_1)//q_1 L.append(a_1) if(a_1==2*L[0]):break p_0,q_0,a_0=p_1,q_1,a_1; print L; r=len(L)-2 if(r%2==0): r=2*r+1 T=L; L[len(L):]=T[1:] a0=int(math.sqrt(D)) p0,p1,p2=L[0],L[0]*L[1]+1,0; q0,q1,q2=1,L[1],0; for i in range(2,r+1): p2=p1*L[i]+p0 q2=q1*L[i]+q0 #print p2,' ',q2 p0,p1=p1,p2 q0,q1=q1,q2; print p1,' ',q1;

Advertisements

No comments yet.

## Leave a Reply