Project Euler — problem 12

July 7, 2012
By

(This article was first published on Tony's bubble universe » R, and kindly contributed to R-bloggers)

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 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, … 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. (n1 of p(rime)1, n2 of p2, …), the sum of divisors is easy to get, which is (n1 + 1) * (n2 + 1)*…*(nlast1 + 1).

?View Code RSPLUS
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.

To leave a comment for the author, please follow the link and comment on their blog: Tony's bubble universe » R.

R-bloggers.com offers daily e-mail updates about R news and tutorials on topics such as: Data science, Big Data, R jobs, visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...



If you got this far, why not subscribe for updates from the site? Choose your flavor: e-mail, twitter, RSS, or facebook...

Tags: , ,

Comments are closed.

Sponsors

Mango solutions



RStudio homepage



Zero Inflated Models and Generalized Linear Mixed Models with R

Quantide: statistical consulting and training

datasociety

http://www.eoda.de





ODSC

ODSC

CRC R books series





Six Sigma Online Training









Contact us if you wish to help support R-bloggers, and place your banner here.

Never miss an update!
Subscribe to R-bloggers to receive
e-mails with the latest R posts.
(You will not see this message again.)

Click here to close (This popup will not appear again)