Project Euler problem #251 defines a Cardano triplet as a triplet of positive integers (a,b,c) such that ∛(a+b√c) + ∛(a-b√c) = 1. We are asked to find the number of Cardano triplets with a+b+c ≤ 110,000,000.
There's a reasonably obvious solution (transform the equation to b2c=(x+1)2(8x+5) where a=3x+2, scan x over the range of possible values, factor the RHS to get values for b and c), and I got the correct answer, but it's rather slow — my code took about 20 hours to run (using Python on a 4 GHz processor), but the site claims that each problem can be solved in under a minute using a not-too-slow language on a not-to-slow computer. So there's surely a better way.
One thing I noticed is that if (a,b,c) constitute a Cardano triplet then, ∛(a±b√c) are quadratic surds — specifically, they are the roots of the polynomial x2-x+(2a-1)/3. Unfortunately, I can't seem to turn this observation into a more efficient enumeration of the triplets.
Can anyone help me devise a faster enumeration?
For the discussion of math. Duh.
1 post • Page 1 of 1
Who is online
Users browsing this forum: No registered users and 9 guests