Project Euler problem 12

Source code available on GitHub.

Here goes:

  The sequence of triangle numbers is generated by adding the natural numbers. So the \(7^{\mathrm{th}}\) triangle number would be \(1 + 2 + 3 + 4 + 5 + 6 + 7 = 28\). The first ten terms would be:

    \[\textrm{1, 3, 6, 10, 15, 21, 28, 36, 45, 55, }\ldots\]

  Let us list the factors of the first seven triangle numbers:

(1)   \begin{align*} \textbf{3: }&1,3 \\ \textbf{6: }&1,2,3,6 \\ \textbf{10: }&1,2,5,10 \\ \textbf{15: }&1,3,5,15 \\ \textbf{21: }&1,3,7,21 \\ \textbf{28: }&1,2,4,7,14,28 \end{align*}

  We can see that 28 is the first triangle number to have over five divisors.  What is the value of the first triangle number to have over five hundred divisors?

Ok, so we’re going to need to be able to find all the factors of a given number. In problem 3 we wrote a function to find all the prime factors:

def primeFactors(number):
    primefactors = []
    while True:
        if isPrime(number):
            primefactors.append(number)
            break
        for i in range(1,math.ceil(math.sqrt(number))+1): # Only check up to the square root: any other factors can be found from the existing ones
            if number % i == 0 and isPrime(i):
                primefactors.append(i)
                number = int(number/i)
                break
    return primefactors

(We wrote the function isPrime(number) to check if number is prime or not.) We can do something similar but much simpler if we don’t care about primality: once we find a factor i of n, we just add both i and n/i (or for best practice, int(n/i)) to our list of factors. Once we’ve got to sqrt(n) we know we have them all.

def findFactors(n):
    factors = []
    for i in range(1,math.floor(math.sqrt(n))+1):
        if n % i == 0:
            factors.append(i)
            factors.append(int(n/i))
    return factors

Next, we make a simple function to find the nth triangular number:

def triangularNumber(n):
    sum = 0
    for i in range(1,n+1):
        sum += i
    return sum

That one’s pretty self-explanatory.

So, now we just have to keep finding triangular numbers, check their factors, and if there are more than 500 of them, print off that triangular number and end the program:

index = 0

while True:
    if len(findFactors(triangularNumber(index))) >= 500:
        print(triangularNumber(index))
        break
    index += 1

Done! Here’s the whole thing:

import math

def findFactors(n):
    factors = []
    for i in range(1,math.floor(math.sqrt(n))+1):
        if n % i == 0:
            factors.append(i)
            factors.append(int(n/i))
    return factors

def triangularNumber(n):
    sum = 0
    for i in range(1,n+1):
        sum += i
    return sum

index = 0

while True:
    if len(findFactors(triangularNumber(index))) >= 500:
        print(triangularNumber(index))
        break
    index += 1

 

Leave a Reply

Your email address will not be published. Required fields are marked *