# Project Euler Problem #12

Problem 12 on the Project Euler site asks:

What is the value of the first triangle number to have over five hundred divisors?

A triangular number T(n) is defined as $$T(n) = \frac{n(n+1)}{2}$$. The R code below consists of a solution, which involves the fact that the number of proper divisors of an integer n can be calculated by first computing a prime factorisation of the number n, e.g. if <$$n = p^aq^b$$, where p,q are prime, then the number of proper divisors of n can be calculated as $$d(n) = (a+1)(b+1)$$. This solution is extremely slow (mainly due to the naive prime sieving algorithm), and could be speeded up dramatically with a little effort. # Sieve of Eratosthenes
prime.sieve <- function(n) {
a <- seq.int(1,n)
p <- 1
M <- as.integer(sqrt(n))
while ((p <- p + 1) <= M) {
if (a[p] != 0)
a[seq.int(p*p, n, p)] <- 0
}
a[a>1 & a>0]
}

# Trial Division
# Returns the exponents of the prime
# factors of n
# e.g. if n = p^a*q^b
# tdiv(n) will return (a,b)
tdiv <- function(n) {
primes <- prime.sieve(n)
factors <- c()
i <- 1
curr <- 0

for (p in primes) {
while (n %% p == 0) {
curr <- curr + 1
n <- n %/% p
}
factors[i] <- curr
i <- i + 1
curr <- 0
}

factors[factors > 0]
}

# Compute nth triangular number
T <- function(n) {
(n*(n+1))/2
}

## Problem 12
# This is a slooow solution
problem12 <- function(N) {
n <- 0 # current triangular number Tn
i <- 5 # \sum_{i=1}^n{i}

while (TRUE) {
n <- T(i)
factors <- tdiv(n)
if (prod(factors+1) >= N) {
return(n)
}
i <- i + 1
}
}