Theory
Calculate prime factors
For a semi-naive approach, you could calculate the prime factors of n
first:
from collections import Counter
from math import floor
def factors(n, found=Counter(), start=2):
if not found:
found = Counter()
for i in range(start, floor(n**0.5)+1):
if n % i == 0:
found[i] += 1
return factors(n // i, found, start=i)
found[n] += 1
return found
The function returns a Counter
, with prime factors as keys and exponent as values:
print(factors(1))
# Counter({1: 1})
print(factors(7))
# Counter({7: 1})
print(factors(24))
# Counter({2: 3, 3: 1})
print(factors(25))
# Counter({5: 2})
print(factors(35))
# Counter({5: 1, 7: 1})
print(factors(1024))
# Counter({2: 10})
Calculate number of divisors
You can then use this counter to calculate the number of divisors:
def number_of_divisors(n):
if n == 1:
return 1
result = 1
for exponent in factors(n).values():
result *= exponent + 1
return result
Example:
print(number_of_divisors(60))
# 12
Solution
You simply need to iterate over n
until the n-th triangle number has more than 500 divisors:
from itertools import count
for n in count():
triangle_number = n * (n + 1) // 2
divisors_count = number_of_divisors(triangle_number)
if divisors_count > 500:
print("The %d-th triangle number is %d and has %d divisors." %
(n, triangle_number, divisors_count))
break
It returns a solution in less than 300ms on my slowish computer:
The 12375-th triangle number is 76576500 and has 576 divisors.
Optimization
- Since
factors
returns a Counter
, you can use the fact that factors(n1*n2)
is factors(n1) + factors(n2)
for any integers n1, n2
larger than 1.
- You could cache the result of
factors(n+1)
, and use it as factors(n)
during the next iteration.
- @vnp has written an excellent answer with further optimization.
The complete code becomes:
from collections import Counter
from math import floor
from functools import lru_cache
from itertools import count
def factors(n, found=Counter(), start=2):
if not found:
found = Counter()
for i in range(start, floor(n**0.5) + 1):
if n % i == 0:
found[i] += 1
return factors(n // i, found, start=i)
found[n] += 1
return found
@lru_cache(maxsize=1024)
def number_of_divisors(n):
if n == 1:
return 1
result = 1
for exponent in factors(n).values():
result *= exponent + 1
return result
for n in count():
if n % 2 == 0:
even = n
odd = n + 1
else:
odd = n
even = n + 1
divisors_count = number_of_divisors(even // 2) * number_of_divisors(odd)
if divisors_count > 500:
print("The %d-th triangle number is %d and has %d divisors." %
(n, even * odd // 2, divisors_count))
break
It is 3 times faster than the previous solution:
The 12375-th triangle number is 76576500 and has 576 divisors.
Just for fun, it also finds the solution for 5000+ divisors in less than a minute:
The 2203200-th triangle number is 2427046221600 and has 5760 divisors.