Euler Problem 12 – Highly divisible triangular number

Highly divisible triangular number

Problem 12

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

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?

This problem is a perfect example of why one should read the question properly. A simple example and it took me so much of time to complete it. I’ll let you know my blunder later in the post.

For this I thought of writing one separate function for calculating factors of a number. So at first I wrote this

getFactors = function(num) {
numvec = numeric()
for (i in seq(floor(num/2)))
if (num %% i == 0)
numvec = append(numvec, i)
#Also append the number itself
numvec = append(numvec, num)
return(numvec)
}

A function which goes from 1 to half of the number since any number cannot be divided by any other number which is more than half of it. For example, 10 has the biggest factor as 5, 18 has the biggest factor as 9 and so on. However, this wasn’t giving me the best efficiency for bigger numbers. So I googled a bit and found another efficient approach.

 getFactors2 = function(num) {
numvec = numeric()
for (i in seq(ceiling(sqrt(num))))
if (num %% i == 0)
numvec =  append(numvec, c(i, num/i))
return(numvec)
}

This basically goes from 1 to the square root of the number and appends two number at a time. The factors are always in pairs. So for example for 24, we have factors as 1, 2, 3, 4, 6, 8, 12 and 24. So here pairs are 1 and 24, 2 and 12, 3 and 8, 4 and 6. This approach uses this method to its advantage and finds such pairs together. Also with this pair methodology we need to only loop till the square root of the number instead of half of it. So, if you want to find factors for 1000 you only need to loop for 32 times instead of 500. This saves whole lot of computation.

The questions reads :

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

As in the example shown for 28, it is the number which is the first triangle number over five divisors. 28 has 6. So, I (wrongly) ‘assumed’ that over 5 divisors has 6 divisors so over 500 should mean find a first triangular number with 501 divisors. So I wrote a code which was checking if the number of divisors was 501 and it took me forever to run the script. With the getFactors function I ran it for 9 hours and it didn’t still produce the result. I was hoping this would run fast with getFactors2 function however, after running the script for 3 hours I realised the mistake.

Over 500 divisors can mean anything which is over 500 i.e 501, 502 anything. By checking only for 501 Is wrong. After that correction, it took me 10 seconds to get the answer. 😉

highly_divisible_triangle_number = function(factorLength) {
  num = 2
  while(TRUE) {
    triangleNumber = sum(seq(num))
    triangleFactors = getFactors2(triangleNumber)
#This is the place where I was making mimstake, using == instead of >
    if(length(unique(triangleFactors)) > factorLength) 
      break
    else
      num = num + 1
  }
  return(triangleNumber)
}

And as correctly thought of the answer 76576500 has 576 divisors which is greater than 500 and is not 501.

Advertisements

One thought on “Euler Problem 12 – Highly divisible triangular number

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s