Project Euler

Everything regarding Project Euler solutions.

16
Feb
2013
Project Euler 136: Singleton difference

Project Euler 136: Singleton difference

Problem 136 of Project Euler can be solved in a very easy way, and a very fast way. So lets look at the problem and dive right into the problem which reads

The positive integers, x, y, and z, are consecutive terms of an arithmetic progression. Given that n is a positive integer, the equation,x2 – y2 – z2 = n, has exactly one solution when n = 20:

132 – 102 – 72 = 20

In fact there are twenty-five values of n below one hundred for which the equation has a unique solution.

How many values of n less than fifty million have exactly one solution?

So this sounds a bit like Problem 135? Well it is a lot like that, and this is where we will get out easy solution from. Continue reading →

Posted by Kristian in Project Euler, 3 comments
09
Feb
2013
Project Euler 135: Same differences

Project Euler 135: Same differences

In Problem 135 of Project Euler we have another nice number theory problem. The problem reads

Given the positive integers, x, y, and z, are consecutive terms of an arithmetic progression, the least value of the positive integer, n, for which the equation, x2 – y2 – z2 = n, has exactly two solutions is n = 27:

342 – 272 – 202 = 122 – 92 – 62 = 27

It turns out that n = 1155 is the least value which has exactly ten solutions.

How many values of n less than one million have exactly ten distinct solutions?

Continue reading →

Posted by Kristian in Project Euler, 14 comments
02
Feb
2013
Project Euler 134: Prime pair connection

Project Euler 134: Prime pair connection

With a little help from Wikipedia I found Problem 134 of Project Euler rather easy to solve.  Well it was easy after solving some issues I had with integer overflows and several other bugs. But anyway, the problem reads

Consider the consecutive primes p1 = 19 and p2 = 23. It can be verified that 1219 is the smallest number such that the last digits are formed by p1 whilst also being divisible by p2.

In fact, with the exception of p1 = 3 and p2 = 5, for every pair of consecutive primes, p2 > p1, there exist values of n for which the last digits are formed by p1 and n is divisible by p2. Let S be the smallest of these values of n.

Find ΣS for every pair of consecutive primes with 5 ≤ p1 ≤ 1000000.

Continue reading →

Posted by Kristian in Project Euler, 5 comments
26
Jan
2013
Project Euler 133: Repunit nonfactors

Project Euler 133: Repunit nonfactors

Problem 133 of Project Euler is a continuation of Problem 132 and Problem 129 in which we are supposed to find the some prime numbers which are not factors of R(10n) for any n. In fact the problem reads

A number consisting entirely of ones is called a repunit. We shall define R(k) to be a repunit of length k; for example, R(6) = 111111.

Let us consider repunits of the form R(10n).

Although R(10), R(100), or R(1000) are not divisible by 17, R(10000) is divisible by 17. Yet there is no value of n for which R(10n) will divide by 19. In fact, it is remarkable that 11, 17, 41, and 73 are the only four primes below one-hundred that can be a factor of R(10n).

Find the sum of all the primes below one-hundred thousand that will never be a factor of R(10n).

Continue reading →

Posted by Kristian in Project Euler, 6 comments
19
Jan
2013
Project Euler 132: Large repunit factors

Project Euler 132: Large repunit factors

In problem 132 of Project Euler we are going back to working with repunits in a problem that reads

A number consisting entirely of ones is called a repunit. We shall define R(k) to be a repunit of length k.

For example, R(10) = 1111111111 = 11 x 41 x 271 x 9091, and the sum of these prime factors is 9414.

Find the sum of the first forty prime factors of R(109).

Continue reading →

Posted by Kristian in Project Euler, 4 comments
12
Jan
2013
Project Euler 131: Determining primes, p, for which n^3 + n^2p is a perfect cube.

Project Euler 131: Determining primes, p, for which n^3 + n^2p is a perfect cube.

I am pretty sure the Problem 131 of Project Euler can be brute forced. However, if you start digging you will see that there is a really beautiful solution to the problem that reads

There are some prime values, p, for which there exists a positive integer, n, such that the expression n3 + n2p is a perfect cube.

For example, when p = 19, 83 + 82x19 = 123.

What is perhaps most surprising is that for each prime with this property the value of n is unique, and there are only four such primes below one-hundred.

How many primes below one million have this remarkable property?

Continue reading →

Posted by Kristian in Project Euler, 4 comments
05
Jan
2013
Project Euler 130: Finding composite values, n, for which n−1 is divisible by the length of the smallest repunits that divide it.

Project Euler 130: Finding composite values, n, for which n−1 is divisible by the length of the smallest repunits that divide it.

Problem 130 of Project Euler is a continuation of problem 129, so if you have already solved that this one should be pretty easy. It reads

A number consisting entirely of ones is called a repunit. We shall define R(k) to be a repunit of length k; for example, R(6) = 111111.

Given that n is a positive integer and GCD(n, 10) = 1, it can be shown that there always exists a value, k, for which R(k) is divisible by n, and let A(n) be the least such value of k; for example, A(7) = 6 and A(41) = 5.

You are given that for all primes, p > 5, that p – 1 is divisible by A(p). For example, when p = 41, A(41) = 5, and 40 is divisible by 5.

However, there are rare composite values for which this is also true; the first five examples being 91, 259, 451, 481, and 703.

Find the sum of the first twenty-five composite values of n for which
GCD(n, 10) = 1 and n – 1 is divisible by A(n).

Continue reading →

Posted by Kristian in Project Euler, 3 comments
29
Dec
2012
Project Euler 129: Investigating minimal repunits that divide by n.

Project Euler 129: Investigating minimal repunits that divide by n.

Problem 129 of Project Euler reads

A number consisting entirely of ones is called a repunit. We shall define R(k) to be a repunit of length k; for example, R(6) = 111111.

Given that n is a positive integer and GCD(n, 10) = 1, it can be shown that there always exists a value, k, for which R(k) is divisible byn, and let A(n) be the least such value of k; for example, A(7) = 6 and A(41) = 5.

The least value of n for which A(n) first exceeds ten is 17.

Find the least value of n for which A(n) first exceeds one-million.

Continue reading →

Posted by Kristian in Project Euler, 7 comments
22
Dec
2012
Project Euler 128: Which tiles in the hexagonal arrangement have prime differences with neighbours?

Project Euler 128: Which tiles in the hexagonal arrangement have prime differences with neighbours?

Problem 128 is a really interesting problem about prime numbers. It reads

A hexagonal tile with number 1 is surrounded by a ring of six hexagonal tiles, starting at “12 o’clock” and numbering the tiles 2 to 7 in an anti-clockwise direction.

New rings are added in the same fashion, with the next rings being numbered 8 to 19, 20 to 37, 38 to 61, and so on. The diagram below shows the first three rings.

By finding the difference between tile n and each its six neighbours we shall define PD(n) to be the number of those differences which are prime.

For example, working clockwise around tile 8 the differences are 12, 29, 11, 6, 1, and 13. So PD(8) = 3.

In the same way, the differences around tile 17 are 1, 17, 16, 1, 11, and 10, hence PD(17) = 2.

It can be shown that the maximum value of PD(n) is 3.

If all of the tiles for which PD(n) = 3 are listed in ascending order to form a sequence, the 10th tile would be 271.

Find the 2000th tile in this sequence.

Continue reading →

Posted by Kristian in Project Euler, 2 comments
15
Dec
2012
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 (a, b, c) to be an abc-hit if:

  1. GCD(a, b) = GCD(a, c) = GCD(b, c) = 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