Project Euler 12: Highly divisible triangular number

[Nick O]

After running into the dilemma of having nothing to do a little while ago, I decided to try working on a Project Euler problem with a mathematical approach. Not being a mathematician, I soon found myself in a rut.

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?

Now, what I have so far is this:

1. Let T(n) be the nth Triangle Number, n > 0.
2. Define f(n) = n for all odd n.
3. Define f(n) = n+1 for all even n.
4. Define g(n) = floor(\frac{n}{2})+1 for all odd n.
5. Define g(n) = \frac{n}{2} for all even n.
6. I have proven by induction that f(n) and g(n) are ALWAYS divisors of T(n).

I have therefore found two persistent sequences in the divisors of the Triangle Numbers. Naturally, all of the divisors of g(n) and f(n) are also divisors of T(n). If both g(n) and f(n) are less than sqrt(T(n)), then we can readily conclude that there are at least twice as many divisors of T(n) as there are of g(n) and f(n).

It was my hope that by analyzing these two sequences, I could find an underlying metasequence that governs the divisors of the triangle numbers, eventually finding a small set of sequences that completely describe the divisors of T(n) when n is below some upper bound. Instead, I have found myself completely unable to detect any further patterns.

At first I toyed with the idea that f(n) and g(n) were the only governing sequences for n > 1, but then I realized that T(8) is a counterexample, because the divisor 6 cannot be derived from those two sequences alone.

So, my question is this: Is there any promise in this approach? If so, could someone give me a gentle nudge in the right direction? I can easily solve this in a short time using a program and prime factorization, but I would love to solve this entirely on paper, if possible.

 

[micromass]

Do you know that the $n$th triangle number is equal to \frac{n(n+1)}{2}

 

[Nick O]

Yes, I used that to prove point 6. Besides suddenly seeing an easier way to prove the relation with f(n) than the proof that I used, I can't think of anything else to do with it.