Blog :: Z'Laast

Problem

This problem comes from Project Euler 12

Problem

The sequence of triangle numbers is generated by adding the natural numbers.

So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:
$1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...$
Let us list the factors of the first seven triangle numbers:

1: 1

3: 1,3

6: 1,2,3,6

10: 1,2,5,10

15: 1,3,5,15

21: 1,3,7,21

28: 1,2,4,7,14,28

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?

Solution

The problem asks us, “What is the value of the first triangle number to have over five hundred divisors?“. This means we have to be able to find the number of divisors for any given number.

We could try dividing the triangle numbers by incrementing integers (for example, attempt to divide the triangle number by 2, 3, 4, 5, 6, 7, 8, … etc.) to get a list of factors, and this would work! But there’s a better way.

What we could do is perform prime factorization, then figure out how many factors exist from that.

Number of Factors

It is known that

\alpha = p_0^{x_0} \times p_1^{x_1} \times p_2^{x_2} \times ... \times p_n^{x_m}

Where

$\alpha$ is the number we are factoring
$p_n$ is a prime factor
$x_m$ is the amount (exponent) of that prime factor

If that is true, then the number of factors of $\alpha$ are

F = (x_0 + 1) \times (x_1 + 1) \times (x_2 + 1) \times ... \times (x_m + 1)

Of course, all of that ✨ jazz ✨ makes absolutely no sense to anyone, so let’s do two examples.

Example 1

Let’s find the number of factors for the number 63. By performing prime factorization, we get

63 = 3 \times 3 \times 7

Which is the same as

63 = 3^2 \times 7^1

We now have the factorization in the form we can use. We can figure out the total number of factors!

F = (2 + 1) \times (1 + 1) = 6

And that’s it. Out of interest, the six factors are 1, 3, 7, 9, 21, and 63, but for the problem, that isn’t important.

Example 2

Let’s find the amount of factors for the number 486 243. Performing prime factorization we get

486 243 = 3^6 \times 23^1 \times 29^1

The number of factors is then

F = (6 + 1) \times (1 + 1) \times (1 + 1) = 28

Code

This is the plan

Perform prime factorization on a triangle number
Count the amount of prime factors the triangle number has
Calculate the total number of factors

# Project Euler: Problem 12
# Highly Divisible Triangular Number

import math
from collections import Counter
from PEF import soe

counter = 1
triangle_number = 1
primes = soe(10)

while True: # Generate Triangle Number
counter += 1
triangle_number += counter

    # Create copy that will be factored
    to_be_factored = triangle_number

    # Perform prime factorization on copy
    prime_factors = []
    for prime in primes:
        while(to_be_factored % prime == 0):
            to_be_factored = to_be_factored // prime
            prime_factors.append(prime)

    # Count the number of factors
    amount_of_factors = math.prod(list(map(lambda prime_count: prime_count + 1, Counter(prime_factors).values())))

    if (amount_of_factors > 500):
        print(triangle_number)
        break

# PEF: Project Euler Functions

import math

def soe(n):
    '''Sieve of Eratosethenes. Finds prime numbers'''

    primes = []
    number_list = [True]*(n+1)

    for i in range(2, n+1):
        if number_list[i]:
            primes.append(i)

            # Eliminate multiples. They aren't prime
            for multiple in range(i**2, n+1, i):
                number_list[multiple] = False
    
    return primes

So, Line 27 is a monstrosity 👹 and not very readable. Honestly, I shouldn’t be programming this way, but I did it as a learning opportunity as I’m not hugely familiar with lambda and map. Regardless, here’s how that one liner works with an example.

While I’m unsure if Example 2 is a triangle number, we’ll use that as our example. The map function has the form map(function, iterable). This uses the function supplied on each element of the iterable.

Our iterable will be Counter(prime_factors).values(), which returns a list of the number of prime factors the triangle number has. Using our example of 486 243, this would return [6, 1, 1].

The function will be the lambda function lambda prime_count: prime_count + 1. It takes the variable prime_count and returns prime_count + 1. With our example, it would return 7, 2, 2.

Our map function has a return type of “map object,” which isn’t useful on its own right now, so we transform it to a list using the list() function. Now we get the list [7, 2, 2].

Finally math.prod() multiplies all elements of a list together, which means $7 \times 2 \times 2 = 28$ .

Project Euler

Problem 12 - Highly Divisible Triangular Number