Posts Tagged with "Coprimes"

Project Euler 12 – Revisited

Saturday, May 14, 2011


A while ago I treated Problem 12 of Project Euler and came up with several solutions as seen here.In relation to that post Nazia asked me if the code would scale, and that made me realise that the current implementation of the function for calculating the number of divisors is dependent on the prime array that I used to be large enough. If this isn't the case the calculated number of divisors may very well be wrong. Besides that, using integers limits the solution to numbers less than approximately 2.7 billion.

Continue reading...

Project Euler 39: If p is the perimeter of a right angle triangle, {a, b, c}, which value, for p ≤ 1000, has the most solutions?

Tuesday, May 3, 2011


Even though the title nor the description of Problem 39 of Project Euler mentions Pythagorean Triplets, this is the topic we are revisiting. The problem description readsIf p is the perimeter of a right angle triangle with integral length sides, {a,b,c}, there are exactly three solutions for p = 120.{20,48,52}, {24,45,51}, {30,40,50}For which value of p ≤ 1000, is the number of solutions maximised?The answer is certainly not p = 1000 which I can state so boldly since we in Problem 9 was given the fact that there only exists 1 triplet with that property.I have found three different approaches to solving this problem. We can brute force it, we can take an arithmetic approach where we rewrite the equations so we only have to work two parameters and check if an equation has an integer solution, and last but not least we can reuse all the work we derived in solving Problem 9 yielding a very efficient solution to the problem.

Continue reading...

Project Euler 12: Triangle Number with 500 Divisors

Friday, December 3, 2010


Problem 12 of Project Euler reads: What is the value of the first triangle number to have over five hundred divisors?I will give you a three step solutions which incrementally improves the solution speed of the problem. The first is a direct approach with trial division to find the divisors. The second and third algorithm builds on prime factorisation and a coprime property of the triangle number.

Continue reading...

A 1000 Pythagorean triplets – Problem 9

Monday, November 15, 2010


Problem 9 of Project Euler states A Pythagorean triplet is a set of three natural numbers, a < b < c, for which, a2 + b2 = c2There exists exactly one Pythagorean triplet for which a + b + c = 1000.Find the product abc.Problem 9 of Project Euler has a widely used brute force approach, which is common on other blogs. Read my blog post to find a detailed explanation to a number theoretical approach as well.

Continue reading...