0
\$\begingroup\$

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
\$\endgroup\$
0

2 Answers 2

4
\$\begingroup\$

Instead of

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

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):    
    return len(set(functools.reduce(list.__add__, 
                                    ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))

if __name__ == "__main__":
    print(next(itertools.filterfalse(lambda x: factors(x) <= 500, triangular_numbers())))

There are more efficient ways of counting factors. A better approach might be to calculate the prime factorization and use that to work out the total number of factors.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.