Project Euler #311

Yay! It’s finally getting hard again! The thrill of many hours of computing and being uncertain whether the result will be correct to the last digit… I love it ;D Now I have to figure out the _correct_ (i.e. non semi-brute-force with smart-ass pruning and nifty little optimizations) method of solving this before I start reading others posts. Some of those guys solved it in mere hours… with code running in minutes or less. I wonder what it could be ;D

ABCD is a convex, integer sided quadrilateral with 1 <= AB < BC < CD < AD.
BD has integer length. O is the midpoint of BD. AO has integer length.
We’ll call ABCD a biclinic integral quadrilateral if AO = CO BO = DO.

For example, the following quadrilateral is a biclinic integral quadrilateral:
AB = 19, BC = 29, CD = 37, AD = 43, BD = 48 and AO = CO = 23.

Let B(N) be the number of distinct biclinic integral quadrilaterals ABCD that satisfy AB2+BC2+CD2+AD2 <= N.
We can verify that B(10 000) = 49 and B(1 000 000) = 38239.

Find B(10 000 000 000).

As a side note – PE #310 was really easy after reading some of the “Winning Ways For Your Mathematical Plays”. I promised to write a review of the book but I’ve been pretty busy lately so it will have to wait. For sure it is a worthwhile publication though, that much I can tell already.

4 Comments

  • I’ve been banging my head against the wall on this one. I coded up my solution and started it running, and thought I might actually get in the top twenty since only a handful of people had submitted answers by then. After hours went by and my program was still churning, I figured out that there must be a reason why there were so few solutions. After a little calculating I realized that my program would need over a month to finish. I still haven’t figured out yet how to prune down the search space sufficiently to get an answer.

  • Frankly speaking my initial solution would also run in unacceptably long time (~200 hours ) if I didn’t have a cluster at my disposal. Only today I’ve been able to reach the correct solution running in several minutes on a regular PC. I was a bit surprised seeing how this one turned out. I suspected it to be more on the ehh hmm… well maybe I’ll stop right here 😉

  • I have coded up a solution to this problem but I estimate it will take about two and a half days to run (if I had enough memory!). Any hints or tips would be greatly appreciated on how to get to a more optimal method. @admin

  • I do not know what they mean by ‘distinct’ here. I can find quadrilaterals up to 10,000 but I seem to have too tight a definition of “equivalent” as it eliminates too many


Leave a Reply

Your email address will not be published. Required fields are marked *