Cardano triplets

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

User avatar
LucasBrown
Posts: 299
Joined: Thu Apr 15, 2010 2:57 am UTC
Location: Poway, CA

Cardano triplets

Postby LucasBrown » Fri Mar 04, 2016 5:51 pm UTC

Project Euler problem #251 defines a Cardano triplet as a triplet of positive integers (a,b,c) such that ∛(a+bc) + ∛(a-bc) = 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±bc) 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?

Return to “Mathematics”

Who is online

Users browsing this forum: pex and 12 guests