Month: August 2014

Problem 031


Project Euler

Coin sums

Problem 31

In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).

It is possible to make £2 in the following way:

1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

How many different ways can £2 be made using any number of coins?


At first, this problem looks very familiar as one of the Combinatorial problem using generating function to solve, such as this:

R(x) = \frac{1}{1-x} \cdot \frac{1}{1-x^2} \cdot \frac{1}{1-x^5} \cdot \frac{1}{1-x^{10}} \cdot \frac{1}{1-x^{20}} \cdot \frac{1}{1-x^{50}} \cdot \frac{1}{1-x^{100}} \cdot \frac{1}{1-x^{200}}

Unfortunately, this seems more complicated to find x^{200} terms than the original problem itself.

Next,  notice the inherently recursive nature of this problem. The problem can be look at using each coin at a time in the following scenario for £2 coin:

  1. Use the £2 coin.
  2. Use no £2 coin.

Each time a coin is used, a similar with smaller value problem arrives. (e.g. How many different ways can £2 be made using any number of coins \rightarrow using one £2 coin \rightarrow How many different way can 0 be made using any number of coins). The problem will recurse down until it finally found the number of ways for 1p, 2p, 3p, … so on, up to £2. Therefore, instead of recurse down, building up using previous result (dynamic programming) maybe more efficient. Using an outer loop for each coins and inner loop for each the amount starting from the coin value, each way of getting to a certain value is being accumulated:

countWayOf[value] += countWayOf[value - COIN[i]];

where value is the index to an array call countWayOf[] that accumulate all the ways that particular value can represent. COIN{} is an array contain the value of each coin and the index i to access that value.

Problem 030


Project Euler

Digit fifth powers

Problem 30

Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits:

1634 = 14 + 64 + 34 + 44
8208 = 84 + 24 + 04 + 84
9474 = 94 + 44 + 74 + 44

As 1 = 14 is not a sum it is not included.

The sum of these numbers is 1634 + 8208 + 9474 = 19316.

Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.


At first glance, using brute force seems to be the most direct way to solve this problem after trying to find some mathematics formula failed. However, even with brute force, an upper limit must be establish to avoid running indefinitely. Following is the relationship between the left and the right side:

10^{n-1} a_n + 10^{n-2} a_{n-1} + \ldots + 10^2 a_3 + 10 a_2 + a_1  = a_n^5 + a_{n-1}^5 + \ldots + a_3^5 + a_2^5 + a_1^5

Let’s list the value of fifth power for all digits:

1^5 = 1
2^5 = 32
3^5 = 243
4^5 = 1024
5^5 = 3125
6^5 = 7776
7^5 = 16807
8^5 = 32768
9^5 = 59049

Notice that if n=1, even the smallest allowable digit (2) will still create a 2-digits number, thus, no 1-digit number is a possible solution. For n=2, any number contains a digit 3 or above is not a solution. For n=3, similarly, any number contains a digit 4 or above is not a solution. For n=4,  any number contains a digit 7 or above is not a solution. For n=5, it is possible to use all digits because 5 \cdot 9^5 = 295245. For n=6, it is also possible to use all digits because 6 \cdot 9^5 = 354294. For n=7, the minimum value on the left side can only be 1000000 but 7 \cdot 9^5 = 413343, which mean there is no possible solution because the largest possible right side value is less than the smallest left side value. Thus, the maximum can set to 354294.

Lastly, one way to speed up the calculation is to store the calculated fifth power of all digits (list above) into memory for fast access to avoid duplicate calculation. Another improvement maybe skips all no solution digits listed above.

Problem 029


Project Euler

Distinct powers

Problem 29

Consider all integer combinations of ab for 2 ≤ a ≤ 5 and 2 ≤ b ≤ 5:

22=4, 23=8, 24=16, 25=32
32=9, 33=27, 34=81, 35=243
42=16, 43=64, 44=256, 45=1024
52=25, 53=125, 54=625, 55=3125

If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

How many distinct terms are in the sequence generated by ab for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?


Using brute force, this problem can be solve by counting all combination of a^b and then sort them to subtract any repeats from the total. This will give a complexity of O(n^2), which for modern computer can be calculate rather quickly for n=100. The total number of terms before removing duplicate can be calculate as (n-1)^2. From the example, the one duplicate being removed, 2^4 = 4^2, has a property that a_j^2 = a_i. We can express this as follow:

(a^2)^b = (a^2)^{b \cdot 1} = (a^2)^{b \cdot \frac{1}{2} \cdot \frac{2}{1}} = (a^{\frac{2}{2}})^{2 \cdot b} = (a)^{2 \cdot b}

There are 9 a_i that satisfy the above condition (2 to 10) with 99/2 = 49 b’s where 2 \cdot b_i <= 100. Let’s extend this to a_j^3 = a_i, a_j^4 = a_i, and so on, up to a_j^6 = a_i. Note 2^7 > 100 and therefore not needed.

(a^3)^b = (a^3)^{b \cdot 1} = (a^3)^{b \cdot \frac{1}{3} \cdot \frac{3}{1}} = (a^{\frac{3}{3}})^{3 \cdot b} = (a)^{3 \cdot b}
(a^4)^b = (a^4)^{b \cdot 1} = (a^4)^{b \cdot \frac{1}{4} \cdot \frac{4}{1}} = (a^{\frac{4}{4}})^{4 \cdot b} = (a)^{4 \cdot b}
\cdots \cdots 

For cube, there are 3 a_i that satisfy the above condition (2 to 4) with 99/3 = 33 b’s where 3\cdot b_i <= 100. For forth power, there are 2 a’s and 24 b’s and so on.

However, this is not all the duplicates. For any a_i that is a cube, fourth, fifth and sixth power of a smaller a_j and the exponents b is divisible by some integer less than the power, there are additional ways to create duplicates. For example, when a_i = a_j^3 and 2 | b_i and \frac{3b_i}{2} <= 100 or b_i \leq 66 but b_i > 33:

(a^3)^b = (a^3)^{b \cdot 1} = (a^3)^{b \cdot \frac{2}{3} \cdot \frac{3}{2}} = (a^{3 \cdot \frac{2}{3}})^{\frac{3}{2} \cdot b} = (a^2)^{\frac{3}{2} \cdot b}

Similar treatment can be done on forth to sixth power but verifying which value of b needs to be included at different fraction of the reduced power will be the key to not over or under count. This is especially important for a_i = 16, 64, 81 where it is a composite integer power of some a_j and also when the numerator and denominator of the exponent fraction has a greatest common divider that is greater than 1.  The advantage is that it runs extremely fast even with large value of a and b.

Problem 028

Project Euler

Number spiral diagonals

Problem 28

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?


Like Problem 1 and Problem 6, this problem can be solve using summation when examine further. Let look at the 3×3 spiral, we can see that the sum is 1+3+5+7+9, or we can rewrite this as 1+2*(3+9), where 3 and 9 is the minimum and maximum value of the square ring with 3, respectively. For 5×5 spiral, we can write the sum as 1+2*[(3+9) + (13+25)]. If you look further, you will see a pattern such that for ixi spiral, the sum is 1+2(3+9+13+25+ \ldots +i^2-3(i-1)+i^2). To represent this as a summation, the summation need to adjust to only include odd number by having i = 2j+1 and using new upper [(1001 – 1)/2 = 500] and lower [(3-1) / 2 = 1] limits:

1+ 2 \sum_{j=1}^{500} (2j+1)^2+ (2j+1)^2 - 3(2j+1-1)

by separating j^2, j and constant terms and pull out the multipliers. We can use the summation formula to obtain the correct answers.

Problem 027


Project Euler

Quadratic primes

Problem 27

Euler discovered the remarkable quadratic formula:

n² + n + 41

It turns out that the formula will produce 40 primes for the consecutive values n = 0 to 39. However, when n = 40, 402 + 40 + 41 = 40(40 + 1) + 41 is divisible by 41, and certainly when n = 41, 41² + 41 + 41 is clearly divisible by 41.

The incredible formula  n² − 79n + 1601 was discovered, which produces 80 primes for the consecutive values n = 0 to 79. The product of the coefficients, −79 and 1601, is −126479.

Considering quadratics of the form:

n² + an + b, where |a| < 1000 and |b| < 1000

where |n| is the modulus/absolute value of n
e.g. |11| = 11 and |−4| = 4

Find the product of the coefficients, a and b, for the quadratic expression that produces the maximum number of primes for consecutive values of n, starting with n = 0.


The combination between a and b seems large at first but can be reduce using logic. First, if n = 0, then b must be a prime. Therefore, by generating a list of prime less than 1000 and include both positive and negative values, there are, 168×2 = 336, numbers to be consider for b. Second of all, consider n = 1, if b is an odd number, then b+1 will be an even number and a must also be an odd number because to generate a large number of prime, we need the final number to be odd (since only one prime is even). If absolute value of b is 2, then a must be even. Therefore, there are 1000 (including both positive and negative) values to be considered as a.

 

Problem 026


Project Euler

Reciprocal cycles

Problem 26

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.


This problem is interesting because there is an element of abstract algebra that looks familiar. The first thing to note is when 10 is divisible by the denominator, there will not be a recurring cycle. Secondly, if any n ever produce a r_i in the following recurring fraction calculation such that 10 ~r_i = 10 or r_j, there is a recurring cycle:

r_0 = 10 ~mod ~d, r_1 = 10 r_0 ~mod ~d, \ldots r_i = 10 r_{i-1} ~mod ~d

For example, 10 mod 6 = 4, 40 mod 6 = 4 … so on.

Now, to get a very long chain, the denominator (d) should be a prime and a large prime as well. Therefore, using a list of prime generated from previous problem (3), going from the largest to smallest, looks for any number that will continuously generate n-1 different remainder. The largest n with this condition will be the answer.

Problem 025


Project Euler

1000-digit Fibonacci number

Problem 25

The Fibonacci sequence is defined by the recurrence relation:

Fn = Fn−1 + Fn−2, where F1 = 1 and F2 = 1.

Hence the first 12 terms will be:

F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
F7 = 13
F8 = 21
F9 = 34
F10 = 55
F11 = 89
F12 = 144

The 12th term, F12, is the first term to contain three digits.

What is the first term in the Fibonacci sequence to contain 1000 digits?


This big integer problem uses similar array of integer (or char) addition strategy found previously. Not able to see any quick mathematical solution, an iterative calculation of each Fibonacci number is used to find the solution. Remember problem 2 where a discussion of Fibonacci number and the golden ratio:

F_n = \frac{\varphi^n - \psi^n}{\sqrt{5}}

where \varphi = \frac{1+\sqrt{5}}{2} and \psi = \frac{1-\sqrt{5}}{2} .

Maybe a quicker solution could come from guess and check different value of n to see which n will produce the answer.