Project Euler 94

gistfile1.txt

# http://projecteuler.net/problem=94
# we're going to solve this using diophantine equations 
# first convert area formula to -3a**2-2a+4c**2+1=0 and -3a**2+2a+4c**2+1=0
# then run that through this solver http://www.alpertron.com.ar/QUAD.HTM to get 2 recursive equations

limit = 1000000000
sum = 0

# a-1 case
a = 1
c = 1
while 3*a-1 < limit:
	a,c = 7*a-8*c+2,-6*a+7*c-2
	area = (0.5*(a-1)*c)/2
	if area == int(area) and a+a+a-1<limit:
		print a,a-1
		sum = sum+3*a-1
		
# a+1 case
a = 1
c = 0
while 3*a-1 < limit:
	a,c = 7*a-8*c-2,-6*a+7*c+2
	area = (0.5*(a+1)*c)/2
	if area == int(area) and a+a+a+1<limit:
		print a,a+1
		sum = sum+3*a+1

# this corrects for first solution which PE considers degenerate
print sum-2