HackerRank Project Euler 12 (Python) | Highly Divisible Triangular Numbers

Question

I again share my Python code which didn't pass time limit test cases in the HackerRank contest of ProjectEuler.

def get_divisors(number):
 divisors = []
 for i in range(1, int(number**0.5) + 1):
 if number % i == 0:
 divisors.append(i)
 if i != number // i:
 divisors.append(number // i)
 return divisors
t = int(input().strip())
for i in range(t):
 n = int(input().strip())
 i = 1
 j = 1
 while True:
 i += 1
 j += i
 if len(get_divisors(j)) > n:
 break
 print(j)

Answer 1

Inaccuracy

Many Project Euler problems deal with BIG numbers. These often are large enough that int(number**0.5) will give you the incorrect result!

Mathematically, \$\lfloor x^{0.5} \rfloor\$ will give you an integer that is less than or equal to the square-root of \$x\$, and squaring that result should return a number less than or equal to the original number. Unfortunately, x ** 0.5 is done using floating-point arithmetic, which has limits to its accuracy. The math module has an integer square-root function which does not suffer from this limitation, because it does not use floating-point numbers.

>>> x = 2 ** 54 - 1
>>> int(x ** 0.5) ** 2 <= x
False
>>> import math
>>> math.isqrt(x) ** 2 <= x
True

The take-away: avoid int(x ** 0.5); always use isqrt(x) instead.

More functions

How can you test your code? You have to run it, and then type in numbers. It would be much easier to test if much of the body of the main script was a function:

def first_triangle_number_with_more_than_n_factors(n):
 i = 1
 j = 1
 while True:
 i += 1
 j += i
 if len(get_divisors(j)) > n:
 break
 return j
t = int(input().strip())
for i in range(t):
 n = int(input().strip())
 j = first_triangle_number_with_more_than_n_factors(n)
 print(j)

Now you can test your function. For example, Project Euler 12 tells you:

We can see that 28 is the first triangle number to have over five divisors.

Using that, we can write a pretty basic test:

assert first_triangle_number_with_more_than_n_factors(5) == 28

Even more functions

The code currently reads:

 if len(get_divisors(j)) > n:

You could change this to:

def num_divisors(j):
 return len(get_divisors(j))
...
 if num_divisors(j) > n:

That's another function, with data from the problem description, so we can write more tests:

assert num_divisors(1) == 1
assert num_divisors(3) == 2
assert num_divisors(6) == 4
assert num_divisors(10) == 4
assert num_divisors(15) == 4
assert num_divisors(21) == 4
assert num_divisors(28) == 6

Optimization

Now we've got several functions, and several tests. We can tell the code is working properly (or not). It is time to optimize it.

We can see we don't actually need the list of divisors, just the number of them. len(get_divisors(j)) works, but it is doing too much work, constructing the divisor list.

Possible replacement function:

def num_divisors(number):
 count = 0
 limit = math.isqrt(number)
 if limit * limit == number:
 count += 1
 else:
 limit += 1
 for i in range(1, limit):
 if number % i == 0:
 count += 2
 return count

Notice the special case of a perfect square was moved outside of the loop, and inside the loop we've no longer got a second if statement. The result should be faster code.

Not Fast Enough

While this is an improvement, it still won't be fast enough. The problem requires knowledge of a mathematical technique for quickly calculating the number of divisors of a number, without actually iterating though all of the divisors.

Research left to student ... but as a hint, prime-factorization will help.

• vnp: A full-blown prime factorization is an overkill here. It is much more important to realize that \$\sigma_0\$ is multiplicative, and that \$n\$ and \$n+1\$ are co-prime. Now (with a little memoization) it is a real speed-up.
• AJNeufeld: @vnp That's true, but is a stronger hint than I was intending to provide.