# My Weblog

## 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;
```