Project Euler Problems Using Python

Problem 25: 1000-digit Fibonacci number

Problem Description

The Fibonacci sequence is defined by the recurrence relation:

$F_n = F_{n-1} + F_{n-2}$, where $F_1 = 1$ and $F_2 = 1$.

Hence the first 12 terms will be:

$F_1 = 1$
$F_2 = 1$
$F_3 = 2$
$F_4 = 3$
$F_5 = 5$
$F_6 = 8$
$F_7 = 13$
$F_8 = 21$
$F_9 = 34$
$F_{10} = 55$
$F_{11} = 89$
$F_{12} = 144$

The 12th term, $F_{12}$, is the first term to contain three digits.

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

Analysis

Based on the definition of Fibonacci sequence, we can easily add new values into this sequence based on the first two values which are $F_1 = F_2 = 1$. This is the process of looping. The termination point of the looping is when there exists a value which contain 1000 digits in the Fibonacci sequence. Then the index of the last value of the sequence is exactly what we need. Since the first index in Python is 0, according to the example in the problem description, where the index of the first term that contains 3 digits is 12, the returning result should be the index plus 1.

This method is not the fastest one, but it can be realized with only the built-in functions of Python. And since 1000 is not a quite large number, the difference in execution time can be ignored.

Solution

Based on the analysis, we can construct a function using Python to solve the generalized problem. The parameter in the self-built function is the resulting number of digits n. To get the result of Euler Project Problem 25, this function can be applied with n set to be 1000. The function and the corresponding annotation are shown below.

def Fibonacci_digit(n):
    """Return the index of the first term in the Fibonacci sequence to contain n digits.
    
    The Fibonacci sequence is defined by the recurrence relation:
        F(n) = F(n-1) + F(n-2), where F(1) = F(2) = 1.
    
    Parameters
    ----------
    n : int
        The resulting number of digits. The Fibonacci sequence at the resulting index is
        desired to contain `n` digits.
        
    Returns
    -------
    int
        The index of the first term in the Fibonacci sequence that contains `n` digits.
        
    Examples
    --------
    The index of the first term in the Fibonacci sequence containing 3 digits.

    >>> Fibonacci_digit(3)
    12
    
    The index of the first term in the Fibonacci sequence containing 1000 digits.
    
    >>> Fibonacci_digit(1000)
    4782
    """
    if n == 1:
        return 1
    
    F = [1,1]
    while len(str(F[-1])) < n:
        F.append(F[-1] + F[-2])
        
    return F.index(F[-1]) + 1

The result we desire is:

>>> Fibonacci_digit(1000)
4782

Therefore, the index of the first term in the Fibonacci sequence to contain 1000 digits is 4782.

Problem 31: Coin sums

Problem Description

In the United Kingdom the currency is made up of pound (£) and pence (p). 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?

Analysis

This is a typical problem that can be solved by dynammic programming. It is quite helpful to consider the numbers of ways to make up different values using different combinations of coins into a table. In this special table, each row represents a different value that we’d like to make up, and each column represents different combinations of coins. The elements in the table mean the number of different ways for the corresponding row and column. This table can be represented as:

In this table, the column ≤20p means the corresponding target values are composed of coins equal or smaller than 20 pence. So the value of the second row and third column shows that there are 2 different ways to make up 2 pence using coin 1p, 2p and 5p. Therefore, our main goal in this problem is to find the value in the 200th row and the last column of the above table.

The first conclusion we can get from the table is that the values within the first column are all 1. This is due to the fact that using only 1-penny coin can merely result in 1 result no matter what the target value is.

Then from the definition of this table, we know that if the maximum denomination in the column is larger than the target value, the corresponding element value will be the same with its left cell. For example, the values between the second column to the last column for target 2p remain the same.

Besides, if the maximum denomination in the column, which we assume to be m, is equal or smaller than the target value, which we assume to be n, the possible combinations can be divided into two parts – One part is the combinations without using m-pence coin, and the other is the combinations using m-pence coin at least once. If we suppose the position of the corresponding element is table[n][j], where j > 1 and i ≥ j, then the first part can be represented by the value of the left cell, table[n][j-1], and the second part can be shown as table[n-m][j]. The reason for the second part is that since we will definitely use at least one m-pence coin, the number of the corresponding combinations will be the same as the number of combinations with target n-m. It doesn’t matter whether the combinations with target n-m use m-pence coins or not, thus the second part is represented as table[n-m][j] rather than table[n-m][j-1].

We can build the entire table through the above properties. However, to make the algorithm more efficient, it is better to conduct manipulations based on a single column rather than the entire table. To make the manipulations possible, from the perspective of table, an extra row needs to be added at the top of the table indexed by 0. All of the values within the extra row is 1.

Thus we can define an objective column with 201 elements, since the target value in Euler Project Problem 31 is £2. The initial values are:

Then we add 2-penny coin onto the stage. The column values with target value equal or greater than 2 should be modified through the rule new_column[i] = old_column[i] + new_column[i-2], where i ≥ 2. Thus the column values become:

We will continue the update until m = 200. Then the last value of the objective column will be the desired result.

Solution

Based on the analysis, a function can be constructed using Python to solve the generalized problem. The parameter in the self-built function is the pool of possible currency denominations coins, which are also the possible ms, and the target value target, which is also n. To get the result of Euler Project Problem 31, we should set coins = [1, 2, 5, 10, 20, 50, 100, 200] as well as target = 200. The function and the corresponding annotation are shown below.

def coin_sum(coins, target):
    """Return the number of combinations of currency denominations.
    
    This function can be used to solve problems like how many different ways can the value
    `target` be made using any number of values within `coins`.
    
    Parameters
    ----------
    coins : array_like
        All possible values that can be used to make up the `target` value. These values 
        should be integers. In the context of currency denomination, all of the values 
        within `coins` should have the same units, which is also the minimum unit. For 
        example, if `coins` contains both penny and pound, the values should be represented
        by pence unit, which accords with the integral requirement.
        
    target : int
        The resulting total value. In the context of currency denomination, it needs to 
        have the same unit with values in `coins`.
        
    Returns
    -------
    int
        The number of possible combinations to make up `target` using values in `coins`.
        
    Examples
    --------
    The number of different ways to make up 2 pounds using 8 possible coins: 1 penny, 
    2 pence, 5 pence, 10 pence, 20 pence, 50 pence, 1 pound, and 2 pounds.

    >>> coin_sum([1, 2, 5, 10, 20, 50, 100, 200], 200)
    73682
    """
    numbers = [1]*(target + 1)
    
    for i in coins[1:]:
        for j in range(i, target+1):
            numbers[j] += numbers[j-i]
            
    return int(numbers[target])

The result we desire is:

>>> coin_sum([1, 2, 5, 10, 20, 50, 100, 200], 200)
73682

Therefore, there are 73682 different ways that £2 can be made using 8 possible coins 1p, 2p, 5p, 10p, 20p, 50p, £1 (100p), and £2 (200p).

Problem 85: Counting rectangles

Problem Description

By counting carefully it can be seen that a rectangular grid measuring 3 by 2 contains eighteen rectangles:

Although there exists no rectangular grid that contains exactly two million rectangles, find the area of the grid with the nearest solution.

Analysis

First of all, we need to specify the number of possible rectangles when the width and length of the grid are x units and y units. Let’s try to get some inspirations by setting y to 1, which will turn the corresponding question into a one-dimensional case.

Thus the number of possible rectangles with grid $x\times1$ is $\frac{x(x+1)}{2}$. The same pattern can be applied to the 2-dimensional case. Therefore, the number of possible rectangles with grid $x\times y$ is the product of $\frac{x(x+1)}{2}$ and $\frac{y(y+1)}{2}$, which lead to $\frac{x(x+1)y(y+1)}{4}$. Then the problem becomes what is the value of $x\times y$ when $\frac{x(x+1)y(y+1)}{4}$ is closest to 2,000,000.

The result can be obtained through traversal. To lower the time cost, we need to find out the maximum width and maximum length of the possible grids if not assigned. Implicitly, the length y is larger than the width x, so the maximum x value can be equal y. In this condition, we have the equation:

$$ \frac{x(x+1)x(x+1)}{4} = 2,000,000 $$

By solving it approximately, the maximum width should be $\left \lceil{(4\times2,000,000)^{1/4}}\right \rceil$, where $\left \lceil{x}\right \rceil$ is the ceiling of x.

Then let’s turn to the maximum length of the possible grids. According to the formula, when x is set to be 1, y will reach its maximum. By solving the equation:

$$ \frac{y(y+1)\times2}{4}=2,000,000 $$

We know that $\left \lceil{(2\times2,000,000)^{1/2}}\right \rceil$ is the maximum length.

Therefore, after calculating all possibilities through looping, where x is from 1 to $\left \lceil{(4\times2,000,000)^{1/4}}\right \rceil$, y is from x to $\left \lceil{(2\times2,000,000)^{1/2}}\right \rceil$, we will get the desired result.

Solution

According to the analysis, a function can be constructed using Python to solve the generalized problem. The parameter in the self-built function is target, which is the target number of possible rectangles, and max_width and max_length, which are defaulted to be None. To get the result of Euler Project Problem 85, we should set target to be 2,000,000. The function and the corresponding annotation are shown below.

def counting(target, max_width = None, max_length = None):
    """Return the area of the grid with the nearest number of possible rectangles compared 
    with `target`.
    
    The sides of the grid and the possible rectangles are integers that are equal or greater 
    than 1. If there exists a grid which contains exactly `target` number of rectangles, the 
    corresponding area will be the returning result. Otherwise, the area of the grid 
    containing the closest number will be returned.
    
    Parameters
    ----------
    target : int
        The desired number of possible rectangles. It should be positive. If no grid has 
        exactly `target` number of rectangles, the grid containing the closest number will 
        be applied.
        
    max_width : int, optional
        The maximum width of the resulting grid. It should be positive. If `max_width` is not 
        given, the value ⌈(4n)^(1/4)⌉, where n is the value of 
        `target`, will be employed based on the following formula.
        
            n = x(x + 1)y(y + 1)/4
        
        Here x and y represent the width and length of the grid. y is implicitly larger 
        than x. Therefore, the maximum value of x is equal to y. After calculation, it 
        should be approximately ⌈(4n)^(1/4)⌉.
        
    max_length : int, optional
        The maximum length of the resulting grid. It should be positive. If `max_length` is 
        not given, the value ⌈(2n)^(1/2)⌉, where n is the value of 
        `target`, will be employed based on the following formula.
        
            n = x(x + 1)y(y + 1)/4
        
        Here x and y represent the width and length of the grid. y is implicitly larger 
        than x. When x is equal to 1, y will reach its maximum value. After calculation, 
        it should be approximately ⌈(2n)^(1/2)⌉.
        
    Returns
    -------
    int
        The area of the grid which has the nearest number of possible rectangles compared 
        with `target`.
        
    Examples
    --------
    The area of the grid with almost two millions number of possible rectangles.

    >>> counting(2000000)
    2772
    """
    if not max_width:
        max_width = int((4*target)**(1/4) // 1 + 1)
    if not max_length:
        max_length = int((2*target)**(1/2) // 1 + 1)
    diff_min = target
    
    for i in range(1, max_width + 1):
        for j in range(i, max_length + 1):
            diff = abs(i*(i+1)*j*(j+1)/4 - target)
            if diff < diff_min:
                area, diff_min = i*j, diff
    
    return area

The result we desire is:

>>> counting(2000000)
2772

Therefore, although there exists no rectangular grid that contains exactly two million rectangles, the area of the grid with the nearest solution is equal to 2772.