My Weblog

Blog about programming and math

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
Advertisements

April 22, 2010 - Posted by | Programming

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: