PE100.gp

/********************************
 * Author:			bigeast
 * Time:			2014-10-18
 * Description:		AC. answer is 756872327473. 8530th.

 佩尔方程，连分数的最优逼近性质

 看了论坛里的讨论(http://forum.projecteuler.net/viewtopic.php?f=50&t=2859)才知
 道思路，是用连分数逼近的性质。不然按暴力搜索的话可能几天都得不到答案，我自己
 运行过三个小时的，没算出来，kill掉了。觉得八千多人做出的题不会这么难算啊。先
 用暴力，求出前几个解，然后找出规律：
.71428571428571428571 = 15/21
.70833333333333333333 = 85/120
.70731707317073170731 = 493/697
.70714285714285714285 = 2871/4060
.70711297071129707112 = 16731/23661
.70710784313725490196 = 97513/137904
.70710696338837042354 = 568345/803761
.70710681244743481917 = 3312555/4684660
 越来越接近1/sqrt(2)，就用它来逼近。而且由于原来的方程(a(a-1))/(b(b-1))=1/2与
 a*a/(b*b)=1/2毕竟是有差别的，所以根据规律，偶数个答案的时候，前者的答案是
 1/2除以后者。比如85/120=17/24的情况，用连分数逼近得到的是12/17。
 ********************************/

{
	b = 1;
	a = 2;
	flag = 0;
	for(n=1,30,
			ta=2*a+b;
			b=a;
			a=ta;
			if(n%2==1,
				blue=a;all=a+b,
				blue=a+b;all=2*a
			  );
			print("(blue,all): ", blue ," ",all);
			for(k=1,10^8,
				kb=k*blue;
				ka=k*all;
				if(ka*(ka-1)==2*kb*(kb-1),
					if(ka>10^12,print("Answer is ",kb);
						flag=1;break,
						print("Actual blue,all",kb," ",ka,"\n")
					  );break
				  );
			   );
			if(flag,break);
	   )
}
/*
{
#
	N = 10;
	bmin = sqrtint(2*N*(N-1)+1)\2;
	b_sq = bmin*bmin;
	for(b=bmin,10^12,
			t = 8*(b_sq-b)+1;
			if(issquare(t),
				tint = sqrtint(t);
				if(tint%2==1,
					n = (tint+1)/2;
					n1 = 2*n*(n-1)+1;
					if(issquare(n1),
						n2 = sqrtint(n1);
						if(n2%2==1,
							print(b," ",n);
						  )
					  )
				  )
			  );
			b_sq += 2*b + 1;
	   );
}
*/