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...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...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...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 reads**If 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.

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...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...
Saturday, December 15, 2012

1 Comment