C#

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, 2 comments
Project Euler 126: Exploring the number of cubes required to cover every visible face on a cuboid.

Project Euler 126: Exploring the number of cubes required to cover every visible face on a cuboid.

Problem 126 of Project Euler is a really awesome geometric challenge. It reads

The minimum number of cubes to cover every visible face on a cuboid measuring 3 x 2 x 1 is twenty-two.

If we then add a second layer to this solid it would require forty-six cubes to cover every visible face, the third layer would require seventy-eight cubes, and the fourth layer would require one-hundred and eighteen cubes to cover every visible face.

However, the first layer on a cuboid measuring 5 x 1 x 1 also requires twenty-two cubes; similarly the first layer on cuboids measuring 5 x 3 x 1, 7 x 2 x 1, and 11 x 1 x 1 all contain forty-six cubes.

We shall define C(n) to represent the number of cuboids that contain n cubes in one of its layers. So C(22) = 2, C(46) = 4, C(78) = 5, and C(118) = 8.

It turns out that 154 is the least value of n for which C(n) = 10.

Find the least value of n for which C(n) = 1000.

Continue reading →

Posted by Kristian in Project Euler, 9 comments
Project Euler 125: Finding square sums that are palindromic

Project Euler 125: Finding square sums that are palindromic

Problem 125 of Project Euler deals with a property we have worked with before, palindromic numbers. The problem reads

The palindromic number 595 is interesting because it can be written as the sum of consecutive squares: 62 + 72 + 82 + 92 + 102 + 112 + 122.

There are exactly eleven palindromes below one-thousand that can be written as consecutive square sums, and the sum of these palindromes is 4164. Note that 1 = 02 + 12 has not been included as this problem is concerned with the squares of positive integers.

Find the sum of all the numbers less than 108 that are both palindromic and can be written as the sum of consecutive squares.

Continue reading →

Posted by Kristian in Project Euler, 4 comments
Project Euler 124: Determining the kth element of the sorted radical function

Project Euler 124: Determining the kth element of the sorted radical function

Problem 124 of Project Euler deals with radical functions, something I have never heard of before. So that always makes it interesting. It 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.
If we calculate rad(n) for 1 ≤ n ≤ 10, then sort them on rad(n), and sorting on n if the radical values are equal, we get:

Unsorted
 
Sorted

n

rad(n)

n

rad(n)

k
1
1
 
1
1
1
2
2
 
2
2
2
3
3
 
4
2
3
4
2
 
8
2
4
5
5
 
3
3
5
6
6
 
9
3
6
7
7
 
5
5
7
8
2
 
6
6
8
9
3
 
7
7
9
10
10
 
10
10
10

Let E(k) be the kth element in the sorted n column; for example, E(4) = 8 and E(6) = 9.

If rad(n) is sorted for 1 ≤ n ≤ 100000, find E(10000). Continue reading →

Posted by Kristian in Project Euler, 7 comments
Project Euler 123: Determining the remainder when (pn − 1)^n + (pn + 1)^n is divided by pn^2

Project Euler 123: Determining the remainder when (pn − 1)^n + (pn + 1)^n is divided by pn^2

Problem 123 of Project Euler reads

Let pn be the nth prime: 2, 3, 5, 7, 11, …, and let r be the remainder when (pn-1)n + (pn+1)n is divided by pn2.

For example, when n = 3, p3 = 5, and 43 + 63 = 280 ≡ 5 mod 25.

The least value of n for which the remainder first exceeds 109 is 7037.

Find the least value of n for which the remainder first exceeds 1010.

Continue reading →

Posted by Kristian in Project Euler, 7 comments
Project Euler 122: Finding the most efficient exponentiation method.

Project Euler 122: Finding the most efficient exponentiation method.

Problem 122 of Project Euler has really proved troublesome for me, partly because I couldn’t read the material I got. But I will get back to that after the problem statement.

The most naive way of computing n15 requires fourteen multiplications:

n x n x … x n = n15

But using a “binary” method you can compute it in six multiplications:

n x n = n2
n2 x n2 = n4
n4 x n4 = n8
n8 x n4 = n12
n12 x n2 = n14
n14 x n = n15

However it is yet possible to compute it in only five multiplications:

n x n = n2
n2 x n = n3
n3 x n3 = n6
n6 x n6 = n12
n12 x n3 = n15

We shall define m(k) to be the minimum number of multiplications to compute nk; for example m(15) = 5.

For 1  k  200, find ∑ m(k).

Continue reading →

Posted by Kristian in Project Euler, 12 comments
Project Euler 121: Investigate the game of chance involving coloured discs

Project Euler 121: Investigate the game of chance involving coloured discs

To be honest, problem 121 of Project Euler scared me a whole lot, since my probability theory is not very strong. However, I do believe that I came up with quite a nice solution after all. The problem reads

A bag contains one red disc and one blue disc. In a game of chance a player takes a disc at random and its colour is noted. After each turn the disc is returned to the bag, an extra red disc is added, and another disc is taken at random.

The player pays £1 to play and wins if they have taken more blue discs than red discs at the end of the game.

If the game is played for four turns, the probability of a player winning is exactly 11/120, and so the maximum prize fund the banker should allocate for winning in this game would be £10 before they would expect to incur a loss. Note that any payout will be a whole number of pounds and also includes the original £1 paid to play the game, so in the example given the player actually wins £9.

Find the maximum prize fund that should be allocated to a single game in which fifteen turns are played.

Continue reading →

Posted by Kristian in Project Euler, 8 comments
Project Euler 120: Finding the maximum remainder when (a − 1)^n + (a + 1)^n is divided by a^2

Project Euler 120: Finding the maximum remainder when (a − 1)^n + (a + 1)^n is divided by a^2

Problem 120 of Project Euler is back in the very mathy part of the questions. Or at least the part where I have been able to find a pretty mathy solution for the problem. It reads

Let r be the remainder when (a-1)n + (a+1)n is divided by a2.

For example, if a = 7 and n = 3, then r = 42: 63 + 83 = 728  42 mod 49. And as n varies, so too will r, but for a = 7 it turns out that rmax= 42.

For 3 ≤ a ≤ 1000, find ∑ rmax.

Continue reading →

Posted by Kristian in Project Euler, 6 comments
Project Euler 119: Investigating the numbers which are equal to sum of their digits raised to some power

Project Euler 119: Investigating the numbers which are equal to sum of their digits raised to some power

Problem 119 of Project Euler reads

The number 512 is interesting because it is equal to the sum of its digits raised to some power: 5 + 1 + 2 = 8, and 83 = 512. Another example of a number with this property is 614656 = 284.

We shall define an to be the nth term of this sequence and insist that a number must contain at least two digits to have a sum.

You are given that a2 = 512 and a10 = 614656.

Find a30.

Continue reading →

Posted by Kristian in Project Euler, 16 comments
Project Euler 118: Exploring the number of ways in which sets containing prime elements can be made.

Project Euler 118: Exploring the number of ways in which sets containing prime elements can be made.

Problem 118 have a very short problem description which in all it’s glory reads

Using all of the digits 1 through 9 and concatenating them freely to form decimal integers, different sets can be formed. Interestingly with the set {2,5,47,89,631}, all of the elements belonging to it are prime.

How many distinct sets containing each of the digits one through nine exactly once contain only prime elements?

Continue reading →

Posted by Kristian in Project Euler, 6 comments