Wednesday, August 6, 2014

Project Euler Problem 12 Solution

Highly divisible triangular number

Problem 12

Published on 08 March 2002 at 06:00 pm [Server Time]
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?



Solution = 76576500




Take Away:

1) To Find Factors of the number n:

instead of going with standard way of checking if n is divisible by every number till n, which has O(n) complexity, we can achieve O(n^0.5).

def get_factors(n):
  ans = [1,n]
  i = 2
  k = n

  while True:

    if i>=k:
      break

    if n%i == 0:
      ans.append(i)
      k = n/i
      if k!=i:
        ans.append(k)

    i = i + 1

  return ans


Explanation:

we can exploit the fact of pairs e.g. 4 is factor of 80, but (4*20) = 80, so we do consider 20 also the factor, and set 20 as threshold.
Now, we will go on increasing 4, 5, and so on, but intuitively, the other end will automatically shrink as factors, right?

4 - 20
5 - 16
8 - 10

here, threshold becomes 10,

when we go for 9, it is not a factor, and when go for 10, which is a threshold, we break, so this way we will never cross beyond square root.

No comments:

Post a Comment