Project Euler problem 12

Source code available on GitHub.

Here goes:

   

(1)  

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