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).
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