Project Euler — problem 12

Going to supper in 20 minutes. I’d like to type down my solution to the 12th Euler problem, just make my time count.

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, … 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?

Here, two issues to be solved. One is to calculate the triangle number, which is simple as we known that nth triangle number, i.e. 1 + 2 + 3 + … + n = n * (n+1) / 2. The other issue is to find out the divisors of one given number, which is harder. The most straightforward way, also the most brute-forced, is to perform division calculations with all the numbers smaller than the given number N. In R, one could use sum((N/1:N) == 0) to get the sum of divisors. Well, it seems we get the solution. Use the first equation to calculate the first triangle number, and check whether the sum of divisors more than 500; if not (definitely not, the first is 1), move on to the next triangle number till you find the result.

However, this is so slow that I could’t take it. Using so-called integer factorization would speed up a lot. Once the list of prime factors is in hand, e.g. (n₁ of p(rime)₁, n₂ of p₂, …), the sum of divisors is easy to get, which is (n₁ + 1) * (n₂ + 1)*…*(n_last1 + 1).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

# helper funtion for factorization		   
PrimeFactor <- function(x, prime = prime) {
  m <- length(prime)
  fac.count <- numeric(m)
  names(fac.count) <- prime
  # actually, a primality check could insert here
  for (i in 1:m) {
    prime.num <- prime[i]
    while (x %% prime.num == 0) {
      fac.count[i] <- fac.count[i] + 1
      x = x / prime.num
    }  
  while (x == 1) break
  }
  return(fac.count)
}
 
prime <- c(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 
           67, 71, 73, 79, 83, 89, 97)
 
# generate triangle numbers and count prime factors
i <- 1
div.count <- 0
while (div.count <= 500) {
	triangle <- i * (i + 1) / 2
	fac <- prime.fac(triangle, prime)
	div.count <- prod(fac + 1) 
	i <- i + 1
}
cat("The result is", i-1, "th triangle number:", triangle, "\n")

Actually, I take some risks here, only using the prime number less than 100, which turned out OK. As it is to find the first triangle number with more than 500 divisors, i.e. the smallest one, the composite number with smaller primes should have bigger chance. And by checking the remainder, the risk of mis-calculation could also be avoided.