# Find the smallest triangular number with more than 500 factors

I wrote a program about triangular numbers, which are derived from the sum of natural numbers one after the other. For example, the third triangular number is equal to: 1 + 2 + 3 = 6.

I want to find divisors of triangular numbers. for example the third triangular number have 4 divisors which equal to : 1,2,3,6.

Some triangular number with their divisors:

• 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

I want to find the smallest triangular number which has more than 500 divisors. This program works, but is too slow to find the 500th. How can I optimize my program?

    def triangular(n):
a= []
for i in range (2,n):
if n % i == 0 :
a.append(i)
if len(a) > 498:
return True
else :
a.clear()
return False
x=1
n=x
while x>0:
if triangular(n):
print(n)
break
else:
n+=x+1
x+=1


        if len(a) > 498:
return True
else :
a.clear()
return False


you could just

        return len(a) > 498


as there's no point in clearing a.

The n-th triangle number is $$\\frac{n(n+1)}{2}\$$, so you could factor both n and n+1 and combine their factorizations.

Takes less than a second:

from collections import Counter
from math import prod
from functools import cache

@cache
def factorize(n):
factorization = Counter()
d = 2
while d * d <= n:
while n % d == 0:
factorization[d] += 1
n //= d
d += 1
if n > 1:
factorization[n] += 1
return factorization

n = triangle = 0
while True:
n += 1
triangle += n
factorization = factorize(n) + factorize(n + 1) - factorize(2)
divisors = prod(power + 1 for power in factorization.values())
if divisors > 500:
print(triangle, divisors)
break

• He starts at 2 and ends at n, so he’s accounting for 1 and n. That’s why he stopped at 498. Jan 25, 2021 at 17:47
• @my_first_c_program Ah, of course, thanks. I removed that remark. Jan 25, 2021 at 17:48
• Do not factorize both n and n+1. Reuse one from the previous iteration.
– vnp
Jan 25, 2021 at 18:13
• @vnp That's what @cache does. Jan 25, 2021 at 18:16

The function triangular() is poorly named. I would recommend writing a function that simply counts factors - and remember that each factor f of n has a corresponding partner n/f, so you only have to count half the factors, and can stop testing above sqrt(n). You might even omit the special case for square n, since triangular numbers can't also be square.

We could write a generator for the triangular numbers, rather than mixing that in to the logic of the main function:

import itertools

def triangular_numbers():
return itertools.accumulate(itertools.count(1))


Then we can just find the first item from that generator which satisfies the condition:

import functools
import itertools

def triangular_numbers():
return itertools.accumulate(itertools.count(1))

def factors(n):

• Could also sum the lists and use a positive filter. Jan 25, 2021 at 17:39