In this article, I would share my solutions to 3 problems of Project Euler using Python. The problems on Project Euler are designed according to the "one-minute rule", which shows that an efficient implementation will allow a solution to be obtained in less then one minute. This is a good website where you can practice designing efficient algorithms for many difficult problems. I will continue to resolve problems on this website and update this blog in the future.

You can find my Github repository for this blog here.

Problem 120: Square Remainders

Let \(r\) be the remainder when \((a−1)^n + (a+1)^n\) is divided by \(a^2\). For example, if \(a = 7\) and \(n = 3\), then \(r = 42: 6^3 + 8^3 = 728 ≡ 42\) mod \(49\). And as \(n\) varies, so too will \(r\), but for \(a = 7\) it turns out that \(r_\mathrm{max} = 42\).

For \(3 \leq a \leq 1000\), find \(\sum r_\mathrm{max}\).

(This problem has been resolved by 13,105 people.)

Solution:

Step 1. Calculate the remainder

I first expand the polynomial for \(n\in \mathbb{N^+}\) \( \begin{aligned} (a+1)^n &= \sum_{i=0}^n C^i_n a^{i}, \\ (a-1)^n &= \sum_{i=0}^n (-1)^{n-i}C^i_n a^{i}, \\ \text{so } (a+1)^n+(a-1)^n &= \sum_{i=0}^n C^i_n a^{i}\left\{1+(-1)^{n-i}\right\}. \end{aligned} \)

From the result, we know that

  • for all odd values of \(n-i\), \(1+(-1)^{n-i}=0\);
  • for all even values of \(n-i\), \(1+(-1)^{n-i}=2\).

Specifically,

  • for all odd \(n\), only those terms with odd \(i\) will remain \((a+1)^n+(a-1)^n = \sum_{i=0}^n C^i_n a^{i}\left\{1+(-1)^{n-i}\right\} = 2 \sum_{i=0}^n C^i_n a^{i} \mathbb{1}_{(i\%2=1)} = 2 \sum_{k=0}^{(n-1)/2} C^{2k+1}_n a^{2k+1};\)

  • for all even \(n\), only those terms with even \(i\) will remain \((a+1)^n+(a-1)^n = \sum_{i=0}^n C^i_n a^{i}\left\{1+(-1)^{n-i}\right\} = 2 \sum_{i=0}^n C^i_n a^{i} \mathbb{1}_{(i\%2=0)} = 2 \sum_{k=0}^{n/2} C^{2k}_n a^{2k}.\)

For all odd values of \(n\), we can see that except for the last term(\(k=0\)), every term is a multiple of \(a^2\). We will then only focus on the last term, \(2 n a\), because only this term is related to the remainder.

Similarly, for all even values of \(n\), every term except for the last one is a multiple of \(a^2\). We will then only focus on the last term, \(2\).

Since \(3 \leq a \leq 1000\), we have \(2 n a \geq 2,\) thus we will only focus on the odd values of \(n\) to learn more about the maximum remainder.

Step 2. Maximize the remainder

For fixed \(a\) and odd \(n\), we try to maximize \(2 n a\) to obtain \(r_\mathrm{max}\). To do this, we can maximize \(n\) by setting \(n\) to be as large as possible to \(a/2\), but will still maintain \(2 n < a\) to keep \(2 n a\) as the remainder of \(a^2\). The problem is reduced to an optimization problem

\[ \begin{aligned} \max_{n} \quad & 2na\\ \textrm{s.t.} \quad & 2n < a \\ & a, n \in \mathbb{N^+} \\ & n\%2 =1 \end{aligned} \]

Note: \(n\%2 =1\) means the remainder of dividing \(n\) by \(2\) is \(1\), i.e., \(n\) is an odd value.

We discuss its solution according to the parity of \(a\),

  • For all odd values of \(a\), the maximum value of \(2 n\) would be \((a-1)\), thus, the maximum value of \(2 n a\) would be \((a-1)a\);
  • for all even values of \(a\), the maximum value of \(2 n\) would be \((a-2)\), thus, the maximum value of \(2 n a\) would be \((a-1)a\).

Therefore,

\[ r_\mathrm{max} = a\{(a-1)\mathbb{1}_{(a\%2=1)} + (a-2)\mathbb{1}_{(a\%2=0)}\} \]

and then

\[ \sum r_\mathrm{max} = \sum_{a=3}^{1000} a\{(a-1)\mathbb{1}_{(a\%2=1)} + (a-2)\mathbb{1}_{(a\%2=0)}\} = \sum_{k=1}^{499} (2k+1) 2k + \sum_{k=1}^{499} (2k+2)2k , \]

where the first term in the right hand side is the sum of all terms with an odd values of \(a\) and the second term is the sum of all terms with an even values of \(a\).

Combine the two terms,

\[ \sum r_\mathrm{max} = \sum_{k=1}^{499} (2k+1) 2k + (2k+2)2k = \sum_{k=1}^{499} (4k+3) 2k. \]

Step 3. Implementation

To compute the above sum, I wrote a function in Python and the correct answer is 333082500.

def sol120(min, max):
    """The sum of (4k+3)*2k for min <= k < max, where k is integer.
    
    Parameters
    ----------
    min : integer
          The value of k of the first term.
    max : integer
          The value of k of the last term.
          
    Returns
    -------
    int
    The sum of terms from k = min to k = max-1.
    """

    return(sum([(4*k+3)*2*k for k in range(min,max)]))

sol120(1,500)

Problem 41: Pandigital Prime

We shall say that an \(n\)-digit number is pandigital if it makes use of all the digits \(1\) to \(n\) exactly once. For example, \(2143\) is a \(4\)-digit pandigital and is also prime.

What is the largest \(n\)-digit pandigital prime that exists?

(This problem has been resolved by 66,749 people.)

Solution:

\(2\) is the only even prime number, and prime numbers that are larger than \(2\) is odd. Obviously, \(2\) is not the largest pandigital prime, so we will only focus on large odd numbers.

Step 1. Check if a number is pandigital

To determine if a number is pandigital, I use the following two criteria:

  • check if the number of digits equals to the number of unique digits,
  • check if the ordered digits is exactly from \(1\) to the largest digit.

In all of the two criteria are satisfied, the number is a pandigital number. Otherwise, the number is not a pandigital number.

Step 2. Check if a number is prime

To determine if a number is prime, I check if the number \(m\) can evenly divide any prime integer \(j\) from \(2\) to \(\sqrt{m}\) (the division leaves no remainder). If \(m\) is divisible by any \(j\), then \(m\) is composite. Otherwise, \(m\) is prime.

Step 3. Check if an odd number is pandigital prime

Since the largest pandigital is less than \(10**10-1\), I will check all odd numbers from \(10**10-1\) (the largest possible number) to \(2143\) (the provided \(4\)-digits pandigital prime).

Step 4. Implementation

The correct answer is 7652413.

def sol41(min, max):
    """Obtain the largest pandigital prime number from [min, max].
    
    Parameters
    ----------
    min : int
          The input number. 
    max : int
          The input number. 
          
    Returns
    -------
    int
    If there exist a pandigital prime number, output the largest one. 
    Otherwise, throw a message.    
    """

    def pandigital(x):
    """Check if a number is pandigital.    """
    digits = [int(x) for x in str(x)]
    if(len(digits) == len(set(digits)) and sorted(digits) == list(range(1, np.max(digits)+1))):
        return(True)
    return(False)
    
    def prime(x):
    """Check if a number is prime.    """
    return(all(x%i!=0 for i in range(2, int(np.sqrt(x))+1)))


    if(min % 2 == 0):  ## check if the provided minimum number is odd
        min = min - 1
    if(max % 2 == 0):  ## check if the provided maximum number is odd
        max = max + 1
    if(min < 2):
        min = 3
    if(max > 10**10):
        max = 10**10-1
    for num in range(max, min, -2): ## check only odd numbers
        if(pandigital(num) and prime(num)):
            return(num)
            break
    print('No pandigital prime number found.')

Problem 13: Large Sum

Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.

37107287533902102798797998220837590246510135740250
46376937677490009712648124896970078050417018260538
...
53503534226472524250874054075591789781264330331690

(This problem has been resolved by 224,947 people.)

Solution:

This problem is not difficult. There are 100 numbers, and each number has 50 digits. To split the numbers, I first store all the numbers in a string and then split the string based on the length of each number. For each number, convert it into an integer. Finally, sum all the numbers and output the first 10 digits of the sum. The correct answer for this problem is 5537376230.

Implementation
def sol13(input, chunk_size, digits):
    """The sum of many large numbers. 
    
    Parameters
    ----------
    input : str
          The string of numbers.
    chunk_size : integer
          The length of each number.
    digits : integer
          The number of digits to keep for the sum.

    Returns
    -------
    int
    The first several digits of the sum.
    """

    ## concatenate input to a string
    x=''.join(input).translate(str.maketrans('','','\n'))
    chunks = len(x)
    ## split numbers
    numbers = [ int(x[i:i+int(chunk_size)]) for i in range(0, chunks, int(chunk_size)) ]
    return(int(str(sum(numbers))[:digits]))
    
sol13(input, 50, 10)