# My Weblog

## Project Euler Problem 140

The analysis of project euler problem 140. Generating function for the problem is
A=(x+3x^2)/(1-x-x^2).
x=-(A+1)+-sqrt((A+1)^2+4A(A+3))/2(A+3) Since x is rational so discriminant must be a perfect square. Discriminant
D=>5P^2+14P+1 =K^2
solving this P=-14+-sqrt(20K^2+176)/10
As P >0 so 20K^2+176 should be perfect square and this lead to pell’s equation of type x^2-dy^=N. Here equation is x^2-20y^2=176. This is general pell’s equation and this page has algorithm to solve this type of equation. Let (p,q) be fundamental solution of x^2-20y^2=176 and (r,s) be the solution of x^2-20y^2=1 then we can generate higher solutions by (pr+-20qs, ps+-qr) . However for equation x^2-20y^2=176 has more than one fundamental solution. So i did some brute force and got three fundamental solution (14,1) (16,2) and (26,5)[or you can use this link to get fundamental solution]. To generate all the higher solutions i computed all the solutions of x^2-20y^2=1 which are (9,2) (161,36) (2889,646) ……20 more according to Xi+1=X1*Xi+20Y1*Yi , Yi+1=X1*Yi+Y1*Xi. Finally generated all the solutions. As this method will not work until you have all the fundamental solution of x^2-Dy^2=N so i am looking for more general solution. Nice problem !

```import math

if __name__=="__main__":
x,y=[],[]
x.append(9)
y.append(2)
for i in range(1,20):
k_1,k_2=x[0]*x[i-1]+20*y[0]*y[i-1],x[0]*y[i-1]+y[0]*x[i-1]
x.append(k_1)
y.append(k_2)
#print x
#print y

p1,q1,p2,q2,p3,q3=[14],[1],[16],[2],[26],[5]
p1.append
for i in range(20):
k_1,k_2,k_3,k_4=p1[0]*x[i]+20*q1[0]*y[i],p1[0]*y[i]+q1[0]*x[i],p1[0]*x[i]-20*q1[0]*y[i],p1[0]*y[i]-q1[0]*x[i]
p1.append(k_1)
p1.append(k_3)
q1.append(k_2)
q1.append(k_4)
k_1,k_2,k_3,k_4=p2[0]*x[i]+20*q2[0]*y[i],p2[0]*y[i]+q2[0]*x[i],p2[0]*x[i]-20*q2[0]*y[i],p2[0]*y[i]-q2[0]*x[i]
p2.append(k_1)
p2.append(k_3)
q2.append(k_2)
q2.append(k_4)
k_1,k_2,k_3,k_4=p3[0]*x[i]+20*q3[0]*y[i],p3[0]*y[i]+q3[0]*x[i],p3[0]*x[i]-20*q3[0]*y[i],p3[0]*y[i]-q3[0]*x[i]
p3.append(k_1)
p3.append(k_3)
q3.append(k_2)
q3.append(k_4)

T=p1
T[len(T):]=p2
T[len(T):]=p3
T.sort();
#print T
ret,sum,cnt=0,0,0
while(True and ret<len(T)):
if((T[ret]-14)%10==0):
cnt+=1
print cnt,' ',(T[ret]-14)/10;
sum+=((T[ret]-14)/10)
if(cnt==31):
print sum;
break;
ret+=1
```