Arithmetic

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 28: What is the sum of both diagonals in a 1001 by 1001 spiral?

Problem 28 of Project Euler reads

Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows:

21 22 23 24 25
20  7  8  9 10
19  6  1  2 11
18  5  4  3 12
17 16 15 14 13

It can be verified that the sum of the numbers on the diagonals is 101.

What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral formed in the same way?

I am pretty sure it is possible to brute force a solution for this problem, but the thought of having to construct the spiral, so let instead of that let us attack it from a more analytical approach and search for a function of the ring number. This is done in two steps, first we will derive a formula where the calculation for the n’th ring depends on the n-1’th ring. And after that we will derive a formula which is independent on the previous ring. Continue reading →

Posted by Kristian in Project Euler, 35 comments

Project Euler 26: Find the value of d < 1000 for which 1/d contains the longest recurring cycle

Problem 26 of Project Euler reads

A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given:

1/2 =
0.5
1/3 =
0.(3)
1/4 = 0.25
1/5
= 0.2
1/6
= 0.1(6)
1/7
= 0.(142857)
1/8
= 0.125
1/9
= 0.(1)
1/10
= 0.1

Where 0.1(6) means 0.166666…, and has a 1-digit recurring cycle. It can be seen that 1/7 has a 6-digit recurring cycle.

Find the value of d < 1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.

How can be possibly approach this problem. Just doing a division and then analysing the double we get out of it is not likely to give us enough digits to find the solution. Usually when the number representation lacks we can use the BigInteger class, but for once that wont help us. However, I found one possible approach. Instead of actually calculating the fraction, we analyse the remainder on each position. It has the advantage that we work with integers rather than fractions.

Continue reading →

Posted by Kristian in Project Euler, 43 comments

Project Euler 23: Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

Problem 23 of Project Euler is about factorisation of a number once again, and has a rather long description. So let me give that to you right away

A perfect number is a number for which the sum of its proper divisors is exactly equal to the number. For example, the sum of the proper divisors of 28 would be 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a perfect number.

A number n is called deficient if the sum of its proper divisors is less than n and it is called abundant if this sum exceeds n.

As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, the smallest number that can be written as the sum of two abundant numbers is 24. By mathematical analysis, it can be shown that all integers greater than 28123 can be written as the sum of two abundant numbers. However, this upper limit cannot be reduced any further by analysis even though it is known that the greatest number that cannot be expressed as the sum of two abundant numbers is less than this limit.

Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

I have only found one effective approach for this problem in C#, there might be more but I haven’t found them. My approach can be summaries in three steps

  1. Find all abundant numbers
  2. Create and mark all number which can be created as the sum of two abundant numbers
  3. Sum up all non-marked numbers

Continue reading →

Posted by Kristian in Project Euler, 23 comments

Project Euler 21: Sum of Amicable Pairs Under 10000

After a few exercises with the focus on other areas, we are in Problem 21 of Project Euler back to focusing on number theory and factorisation. The problem reads

Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
If d(a) = b and d(b) = a, where ab, then a and b are an amicable pair and each of a and b are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

Evaluate the sum of all the amicable numbers under 10000.

Continue reading →

Posted by Kristian in Project Euler, 14 comments

Project Euler 12: Triangle Number with 500 Divisors

Problem 12 of Project Euler has a wording which is somewhat different than previous problems. However, as we shall see deriving efficient solutions for the problem, we can use theory which is very similar to some of the previous problems.  The problem reads

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …

Let us list the factors of the first seven triangle numbers:

1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28
We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

Continue reading →

Posted by Kristian in Project Euler, 31 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, 37 comments

Project Euler – Problem 7

Now we reached Problem 7 of Project Euler which is about prime numbers. The problem reads

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10001st prime number?

We could solve this by brute force checking all the numbers, or we could reuse part of the solution to problem 5, where we generated a list of primes using trial division with already found prime numbers. I haven’t found a way to solve this without finding the 10000 primes before finding the answer.

Wikipedia comes with a great article about prime numbers, which also refers to several methods for checking if a number is a prime. We will take a bit of simpler approach though. But dive into the article, it is pretty interesting.

Continue reading →

Posted by Kristian in Project Euler, 9 comments

Project Euler – Problem 6

This exercise has a longer problem description than the previous, so lets jump right into it.

The sum of the squares of the first ten natural numbers is,

12 + 22 + … + 102 = 385
The square of the sum of the first ten natural numbers is,

(1 + 2 + … + 10)2 = 552 = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 – 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

Continue reading →

Posted by Kristian in Project Euler, 8 comments