Creative Scratchpad

A new day, new Project Euler challenge, who would guess that after problem No. 11 comes problem No. 12:

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?

So, we will need a function to count divisors of a number, that's for sure. If we look in detail on the method to get a number of all the positive divisors of a value, we soon find out that it can be broken into getting the prime factors of a number and multiplying their powers increased by one. We've already done a similar thing with the primeFactorsPow function. This time there's no need to keep an array of the values as we only work with individual numbers. Also, as the powers are to be increased by one, the pow variable is initialized with a value of 1L instead of 0L:

fn countDivisors nr count:1 =
(
    if isEven nr do
    (
        local pow = 1L
        do (nr /= 2L; pow += 1) while isEven nr
        count *= pow
    )

    local rootN = nr^0.5

    for i = 3 to rootN by 2
        where mod nr i == 0 do
    (
        local pow = 1L
        do (nr /= i; pow += 1) while mod nr i == 0
        count *= pow
    )

    if nr > 1 do
        count *= 2

    count
)

But wait, do we really have to count the divisors for each and every number? Let's have a look at what we are dealing with, what are the properties of the triangle numbers that we could use? The infographic on the right says that Tn equals (n × (n+1))/2. The proof here is quite simple, when you take the triangle that represents the number Tn, mirror it and put them together, this is what you will get (for n = 4):

As each element represents an addition of one (i.e. row of four elements equals four), the rectangle contains n × (n+1) elements, and as it is double the size we need, by dividing it by two, we get our result. So it's always a multiplication and we could use it to our advantage as the total number of positive divisors of n is a multiplicative function d(n), e.g. d(42) = 8 = 2 × 2 × 2 = d(2) × d(3) × d(7). The difference here is that we have (n × (n+1))/2 and not just n × (n+1). But there's always one of those values that's even, as they differ exactly by one, so we can just take the even one (once again using the isEven function) and divide it by two:

fn countTriangleDivisors nr =
(
    if isEven nr then
        (countDivisors (nr/2)) * (countDivisors (nr+1))
    else (countDivisors nr) * (countDivisors ((nr+1)/2))
)

To wrap it all together in a nice package we only have to write the for loop (I've started with seven here as the biggest triangle number in the description was the seventh in order) and exit with nthTriangle:

(
    local inf = 1.0/0.

    fn isEven nr = bit.and 1L nr == 0

    fn countDivisors nr count:1 =
    (
        if isEven nr do
        (
            local pow = 1L
            do (nr /= 2L; pow += 1) while isEven nr
            count *= pow
        )

        local rootN = nr^0.5

        for i = 3 to rootN by 2
            where mod nr i == 0 do
        (
            local pow = 1L
            do (nr /= i; pow += 1) while mod nr i == 0
            count *= pow
        )

        if nr > 1 do
            count *= 2

        count
    )

    fn countTriangleDivisors nr =
    (
        if isEven nr then
            (countDivisors (nr/2)) * (countDivisors (nr+1))
        else (countDivisors nr) * (countDivisors ((nr+1)/2))
    )

    fn nthTriangle n = (n^2+n)/2

    for i = 7 to inf
        where countTriangleDivisors i > 500 do
            exit with nthTriangle (integer64 i)
)

It could use some work to make the preformance better, though. Note that there would be no significant speed gain (if any) if we would store previous results of our iterative countDivisors function but it could be an important factor if using recursive version of the same function.

DISCLAIMER: All scripts and snippets are provided as is under Creative Commons Zero (public domain, no restrictions) license. The author and this blog cannot be held liable for any loss caused as a result of inaccuracy or error within these web pages. Use at your own risk.