Highly Divisible Triangle Number

Problem 12

The sequence of triangle numbers is generated by adding the natural numbers. So the \(7^{\text{th}}\) 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:

\[ \begin{align*} 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 \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?

Let’s solve this problem using Julia

We can start by creating two functions

• TriangleNumber(n): This function will compute the nth triangle number
• CountDivisors(n): This function will compoute the number of divisors of n.

Code

function TriangleNumber(n)
    # Compute the nth triangle number
    triangle_number = 1

    if n == 1
        return triangle_number
    else
        for i = 2:n
            triangle_number = triangle_number + i
        end
    end

    return triangle_number
end

TriangleNumber (generic function with 1 method)

Let’s check our function to check for the correct triangle number

Code

println("The 5th triangle number is ", TriangleNumber(5))
println("The 6th triangle number is ", TriangleNumber(6))
println("The 7th triangle number is ", TriangleNumber(7))

The 5th triangle number is 15
The 6th triangle number is 21
The 7th triangle number is 28

Now let’s create the CountDivisors(n) function

Code

function CountDivisors(n)
    count = 1
    if n == 1
        count = 1
    elseif n == 2
        count = 2
    else
        for i = 2:n
            if n%i == 0
                count = count + 1
            end
        end
    end
    return count
end 

CountDivisors (generic function with 1 method)

Let’s test this function to check for the correct number of divisors

Code

println("3 has ", CountDivisors(3), " divisors")
println("4 has ", CountDivisors(4), " divisors")
println("28 has ", CountDivisors(28), " divisors")

3 has 2 divisors
4 has 3 divisors
28 has 6 divisors

Let’s now run a script to compute the first triangle with over \(500\) divisors

Code

index = 0
triangle_number = 0 
while true
    index = index + 1
    triangle_number = TriangleNumber(index)
    if CountDivisors(triangle_number) > 500
        break
    end
end
triangle_number

76576500

Code

CountDivisors(76576500)

576

Therefore the first triangle number to have over 500 divisors is \(76,576,500\) and it has \(576\) divisors.