Brute Force

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
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
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
UVa 102: Ecological Bin Packing

UVa 102: Ecological Bin Packing

We’re back to doing another simple UVa Online Judge problem, and this time we take on problem 102, Ecological Bin Packing. In the problem we are asked to solve a bin packing problem about recycling glass. It can be easily solved with brute force, but requires careful coding. Enough yapping, let’s take a look at the problem description.

Interpretation

We have three bins, each of which contains some number of bottles. There are three types of bottles; brown, green and clear, denoted by “B”, “G” and “C”, respectively. We are given how many  bottles of each type are in each bin. Continue reading →

Posted by Bjarki Ágúst in UVa Online Judge, 1 comment
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
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
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