What's the most efficient way to find factors in a list?
<h2>What I'm looking to do:</h2>

<p>I need to make a function that, given a list of positive integers (there can be duplicate integers), counts all triples (in the list) in which the third number is a multiple of the second and the second is a multiple of the first:</p>

<p>(The same number cannot be used twice in one triple, but can be used by all other triples)</p>

<p>For example, <code>[3, 6, 18]</code> is one because <code>18</code> goes evenly into <code>6</code> which goes evenly into <code>3</code>.</p>

<p>So given <code>[1, 2, 3, 4, 5, 6]</code> it should find:</p>

<pre><code>[1, 2, 4] [1, 2, 6] [1, 3, 6]
</code></pre>

<p>and return <code>3</code> (the number of triples it found)</p>

<h2>What I've tried:</h2>

<p>I made a couple of functions that work but are not efficient enough. Is there some math concept I don't know about that would help me find these triples faster? A module with a function that does better? I don't know what to search for...</p>

<pre><code>def foo(q):
    l = sorted(q)
    ln = range(len(l))
    for x in ln:
        if len(l[x:]) &gt; 1:
            for y in ln[x + 1:]:
                if (len(l[y:]) &gt; 0) and (l[y] % l[x] == 0):
                    for z in ln[y + 1:]:
                        if l[z] % l[y] == 0:
                            ans += 1
    return ans
</code></pre>

<p>This one is a bit faster:</p>

<pre><code>def bar(q):
    l = sorted(q)
    ans = 0
    for x2, x in enumerate(l):
        pool = l[x2 + 1:]
        if len(pool) &gt; 1:
            for y2, y in enumerate(pool):
                pool2 = pool[y2 + 1:]
                if pool2 and (y % x == 0):
                    for z in pool2:
                        if z % y == 0:
                            ans += 1
    return ans
</code></pre>

<p>Here's what I've come up with with help from y'all but I must be doing something wrong because it get's the wrong answer (it's really fast though):</p>

<pre><code>def function4(numbers):
    ans = 0
    num_dict = {}
    index = 0
    for x in numbers:
        index += 1
        num_dict[x] = [y for y in numbers[index:] if y % x == 0]

    for x in numbers:
        for y in num_dict[x]:
            for z in num_dict[y]:
                print(x, y, z)
                ans += 1

    return ans
</code></pre>

<p>(<code>39889</code> instead of <code>40888</code>) - oh, I accidentally made the index var start at 1 instead of 0. It works now.</p>

<h1>Final Edit</h1>

<p>I've found the best way to find the number of triples by reevaluating what I needed it to do. This method doesn't actually find the triples, it just counts them.</p>

<pre><code>def foo(l):
    llen = len(l)
    total = 0
    cache = {}
    for i in range(llen):
        cache[i] = 0
    for x in range(llen):
        for y in range(x + 1, llen):
            if l[y] % l[x] == 0:
                cache[y] += 1
                total += cache[x]
    return total
</code></pre>

<p>And here's a version of the function that explains the thought process as it goes (not good for huge lists though because of spam prints):</p>

<pre><code>def bar(l):
    list_length = len(l)
    total_triples = 0
    cache = {}
    for i in range(list_length):
        cache[i] = 0
    for x in range(list_length):
        print("\n\nfor index[{}]: {}".format(x, l[x]))
        for y in range(x + 1, list_length):
            print("\n\ttry index[{}]: {}".format(y, l[y]))
            if l[y] % l[x] == 0:
                print("\n\t\t{} can be evenly diveded by {}".format(l[y], l[x]))
                cache[y] += 1
                total_triples += cache[x]
                print("\t\tcache[{0}] is now {1}".format(y, cache[y]))
                print("\t\tcount is now {}".format(total_triples))
                print("\t\t(+{} from cache[{}])".format(cache[x], x))
            else:
                print("\n\t\tfalse")
    print("\ntotal number of triples:", total_triples)
</code></pre>

<p>Right now your algorithm has O(N^3) running time, meaning that every time you double the length of the initial list the running time goes up by 8 times.</p>

<p>In the worst case, you cannot improve this. For example, if your numbers are all successive powers of 2, meaning that every number divides every number grater than it, then every triple of numbers is a valid solution so just to print out all the solutions is going to be just as slow as what you are doing now.</p>

<p>If you have a lower "density" of numbers that divide other numbers, one thing you can do to speed things up is to search for pairs of numbers instead of triples. This will take time that is only O(N^2), meaning the running time goes up by 4 times when you double the length of the input list. Once you have a list of pairs of numbers you can use it to build a list of triples.</p>

<pre><code># For simplicity, I assume that a number can't occur more than once in the list.
# You will need to tweak this algorithm to be able to deal with duplicates.

# this dictionary will map each number `n` to the list of other numbers
# that appear on the list that are multiples of `n`.
multiples = {}
for n in numbers:
   multiples[n] = []

# Going through each combination takes time O(N^2)
for x in numbers:
   for y in numbers:
     if x != y and y % x == 0:
         multiples[x].append(y)

# The speed on this last step will depend on how many numbers
# are multiples of other numbers. In the worst case this will
# be just as slow as your current algoritm. In the fastest case
# (when no numbers divide other numbers) then it will be just a
# O(N) scan for the outermost loop.
for x in numbers:
    for y in multiples[x]:
        for z in multiples[y]:
            print(x,y,z)
</code></pre>

<p>There might be even faster algorithms, that also take advantage of algebraic properties of division but in your case I think a O(N^2) is probably going to be fast enough.</p>

python algorithm