Posts Tagged with "Greatest Common Divisor"


Project Euler 127: Investigating the number of abc-hits below a given limit.

Saturday, December 15, 2012

1 Comment

Problem 127 of Project Euler is a really awesome number theoretic problem using concepts of GCD and radicals. The problem reads The radical of n, rad(n), is the product of distinct prime factors of n. For example, 504 = 23 x 32 x 7, so rad(504) = 2 x 3 x 7 = 42. We shall define the triplet of positive integers (a, b, c) […]

Continue reading...

GCD faceoff

Wednesday, April 11, 2012


Recently I received an email from a guy named Alexandr who reads the blog. He send me a small piece of C# code with the statement that my Greatest Common Denominator (GCD) algorithm was not as efficient as it could be. As a side note this algorithm is  also known as greatest common factor GCF and highest common factor HCF. To my defense I would like to state that I do believe that even my implementation of the algorithm is sufficiently good to solve most problems and it is a really good enough.Being the geek that we all are it peeked my interest and I wanted to look a bit into it and test which one was faster as well as open the question for you to give your favorite GCD algorithm.

Continue reading...
Project Euler 73: How many fractions lie between 1/3 and 1/2 in a sorted set of reduced proper fractions?

Project Euler 73: How many fractions lie between 1/3 and 1/2 in a sorted set of reduced proper fractions?

Saturday, December 3, 2011


Problem 73 of Project Euler is the third problem in a row which treats ordering proper fractions. The problem description readsHow many fractions lie between 1/3 and 1/2 in the sorted set of reduced proper fractions for d ≤ 12,000?I solved this in two different ways. Due to the small upper bound I attacked it bruteforce and with a somewhat smarter solution using Farey sequences. Something I have heard mentioned in many previous solutions but only just now started reading up on.

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 33: Discover all the fractions with an unorthodox cancelling method

Saturday, March 26, 2011


Problem 33 of Project Euler is a really fun little problem. At least I think so. It reads The fraction 49/98 is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that 49/98 = 4/8, which is correct, is obtained by cancelling the 9s. If the product of these four fractions is given in its lowest common terms, find the value of the denominator. The problem itself is rather easy to solve using brute force since there are less than 90*90 = 8100 possible solutions we would have to check. Each check is fairly easy to perform and thus we would be able to brute force comfortably within the 1 minute range.

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...