Finding a numbers knowing some some of their divisors-CodePudding

I'm in the process of solving this kata at cw link for the kata, where the objective is to find a way to first generate some triangular numbers and then find numbers that will have all of the pre-generated triangular numbers as their divisors.

My code:

def checker(k,lst):
for num in lst:
    if k%num == 0:
        pass
    if k%num != 0:
        return
return True

def sum_mult_triangnum(n, m):
#creating a list that will store final values
fin = []
#creating a list of Tn numbers 
lst = [n* (n 1) / 2 for n in range(1,n 1)]
#strating to search for all the multiples
k = lst[-1]
while True:
    if checker(k,lst) == True:
        fin.append(k)
        break
    else:
        k = k   lst[-1]
for i in range(m-1):
    fin.append(fin[-1]   fin[0])
#finding sum of multiples 
sum_of_multiples = sum(fin)
return sum_of_multiples

Example:

n = 5
m = 8 
sum_mult_triangnum(n, m) = 1080

list of  triangular numbers = [1, 3, 6, 10, 15]
list of suitable numbers = [30, 60, 90, 120, 150, 180, 210, 240]

In fact, by looking at the given examples we will see that by finding the first suited number we are able to easily generate any amount of following numbers like this:

next number = previous number first suitable number

My code focuses on finding the first suitable number by brute forcing through all the numbers starting from the biggest of generated triangular numbers. It gives correct result, but the problem is in time, so is there any way to speed up the process of finding the first suitable number ?

CodePudding user response：

you ca try to implement this algorithm.

another optimization you can do is to run this algorithm for the numbers from 2 to n 1 and divide the result by two. It will give you the same result than doing it on the n first triangular numbers.

explanation :

to simplify the formula, lets multiply it by 2 : n*(n 1)
the sequence obtained is : (1*2, 2*3, 3*4, ..., n*(n 1))
taking the LCM of this sequence is the same of taking it from this one : (1, 2, 3, ..., n 1) because of all the common factors between the terms next to ech other.
you can ignore the 1 since it doesn't influence the result and slows down the execution : (2, 3, ..., n 1)
the result must be divided by 2 because of the simplification made at the beginning.