Greatest Common Divisor

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

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

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 (abc) to be an abc-hit if:

  1. GCD(a, b) = GCD(ac) = GCD(bc) = 1
  2. a < b
  3. a + b = c
  4. rad(abc) < c

For example, (5, 27, 32) is an abc-hit, because:

  1. GCD(5, 27) = GCD(5, 32) = GCD(27, 32) = 1
  2. 5 < 27
  3. 5 + 27 = 32
  4. rad(4320) = 30 < 32

It turns out that abc-hits are quite rare and there are only thirty-one abc-hits for c < 1000, with c = 12523.

Find c for c < 120000.

Continue reading →

Posted by Kristian in Project Euler, 1 comment
GCD faceoff

GCD faceoff

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 →

Posted by Kristian in Programming, 22 comments
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?

Problem 73 of Project Euler is the third problem in a row which treats ordering proper fractions. The problem description reads

Consider the fraction, n/d, where n and d are positive integers. If n<d and HCF(n,d)=1, it is called a reduced proper fraction.

If we list the set of reduced proper fractions for d ≤ 8 in ascending order of size, we get:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

It can be seen that there are 3 fractions between 1/3 and 1/2.

How many fractions lie between 1/3 and 1/2 in the sorted set of reduced proper fractions for d ≤ 12,000?

Note: The upper limit has been changed recently.

Continue reading →

Posted by Kristian in Project Euler, 11 comments

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?

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?

Continue reading →

Posted by Kristian in Project Euler, 5 comments

Project Euler 33: Discover all the fractions with an unorthodox cancelling method

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.

We shall consider fractions like, 30/50 = 3/5, to be trivial examples.

There are exactly four non-trivial examples of this type of fraction, less than one in value, and containing two digits in the numerator and denominator.

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 →

Posted by Kristian in Project Euler, 9 comments

A 1000 Pythagorean triplets – Problem 9

Today’s problem in Project Euler, is related to probably THE most well known theorem of all times.  Pythagoras theorem stating that Geometric interpretation of Pythagoras

The square of the hypotenuse is the sum of squares of the two other sides.

It can also be stated in a more geometrical way as

In any right triangle, the area of the square whose side is the hypotenuse (the side opposite the right angle) is equal to the sum of the areas of the squares whose sides are the two legs (the two sides that meet at a right angle

Which can also be shown in a graphical sense, on the figure to the right, where the blue area equals the orange area.

But enough with the background info, the problem reads

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,

a2 + b2 = c2

For example, 32 + 42 = 9 + 16 = 25 = 52.

There exists exactly one Pythagorean triplet for which a + b + c = 1000.

Find the product abc.

Continue reading →

Posted by Kristian in Project Euler, 36 comments