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:
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?
Again.. before judging my code, I was learning Python and had no REAL prior experience with coding other than some AP computer science class, but that was more gears toward learning OOP than anything else. I think it's nice to see the progression in learning algorthim and data structure. I solved this problem couple of months ago.
Anyhow, my idea to essentially was to use Fermat's theorem again and to find the factorso of each triangular number. By finding each prime that exists, along with the power associated with each prime, we can use number of factors formula to find the number of divisors:
$$\sigma_0(n) = \Pi_{i=1}^n (a_i + 1)$$ where ai represents powers associated with pi (a prime)
The proof of this function is pretty simple. Using Fundmanetl theomre of rhtimetic states that every integer greater 1 can be uniquely factorized into set of primes. Hence, each divisor of a number can be uniquely prime factorize. So, if two numbers differ by a single prime, they are different. So, for each prime, we have one more than the power of that prime number of choices (i.e 24 has 5 different possibilities, since we can either pick 0, 1, 2, 3, 4 of the factors of 2). This can be repeatedly done for each prime that exists in a number and we just multiply each possibilities!
Answer: 76576500
Runtime: 10 seconds