Problem Description

The sequence of triangle numbers is generated by adding the natural numbers. So the 7^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:

 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?

Analysis

Our algorithm for solving this one was improved nicely by a detailed explanation provided by a Project Euler moderator named ‘rayfil’. His wonderful explanation is published as a PDF document that is available after you solve the problem. What follows is our own interpretation written in Python.

Solution

Runs < 1 second in Python.

def expx(n,p):
  exp=1
  while n % p == 0: 
    exp+=1; 
    n = n/p
  return n,exp
 
def prime_exp(n):
  dx = 1
  for p in primes: 
    if p*p > n: return dx * 2 
    n,exp=expx(n,p)
    dx*= exp
    if n==1: break
  return dx
 
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
nx=3
dx=2 
ndiv=0
max_div = 500
while ndiv <= max_div: 
  nx+= 1 
  dxx = prime_exp(nx/2 if nx % 2 == 0 else nx)
  ndiv, dx = dx*dxx, dxx 
print "Answer to PE12 = ", nx*(nx-1)/2

Comments