Solution to Project Euler Problem 12: Highly divisible triangular number - 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?
Updated: March 7, 2021 — Training Time: 3 minutes
Overseen by: Archangel Macsika
All Training Resources
Scroll for more menu list
Topic: Project Euler Problem 12: Highly divisible triangular number.
Difficulty: Easy.
Objective: 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?
Input: None.
Expected Output: 76576500.
Sikademy Solution in Java Programming Language
package sikademy;
/**
*
* @author Archangel Macsika
* Copyright (c) Sikademy. All rights reserved
*/
public class SikademyEulerSolution {
public String run() {
int triangle = 0;
for (int i = 1; ; i++) {
if (Integer.MAX_VALUE - triangle < i)
throw new ArithmeticException("Overflow");
triangle += i;
if (countDivisors(triangle) > 500)
return Integer.toString(triangle);
}
}
public static int sqrt(int x) {
if (x < 0)
throw new IllegalArgumentException("Square root of negative number");
int y = 0;
for (int i = 1 << 15; i != 0; i >>>= 1) {
y |= i;
if (y > 46340 || y * y > x)
y ^= i;
}
return y;
}
// Returns the number of integers in the range [1, n] that divide n.
private static int countDivisors(int n) {
int count = 0;
int end = sqrt(n);
for (int i = 1; i < end; i++) {
if (n % i == 0)
count += 2;
}
if (end * end == n) // Perfect square
count++;
return count;
}
public static void main(String[] args) {
SikademyEulerSolution solution = new SikademyEulerSolution();
System.out.println(solution.run());
}
}
Sikademy Solution in Python Programming Language
#
# @author Archangel Macsika
# Copyright (c) Sikademy. All rights reserved.
#
import itertools
def sqrt(x):
assert x >= 0
i = 1
while i * i <= x:
i *= 2
y = 0
while i > 0:
if (y + i)**2 <= x:
y += i
i //= 2
return y
def compute():
triangle = 0
for i in itertools.count(1):
triangle += i # This is the ith triangle number, i.e. num = 1 + 2 + ... + i = i * (i + 1) / 2
if num_divisors(triangle) > 500:
return str(triangle)
# Returns the number of integers in the range [1, n] that divide n.
def num_divisors(n):
end = sqrt(n)
result = sum(2
for i in range(1, end + 1)
if n % i == 0)
if end**2 == n:
result -= 1
return result
if __name__ == "__main__":
print(compute())