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>the key insight is:</p>

<p>if <strong>a</strong> divides <strong>b</strong>, it means <strong>a</strong> "fits into <strong>b</strong>".
if <strong>a</strong> doesn't divide <strong>c</strong>, then it means "<strong>a</strong> doesn't fit into <strong>c</strong>".
And if <strong>a</strong> can't fit into <strong>c</strong>, then <strong>b</strong> cannot fit into <strong>c</strong> (imagine if <strong>b</strong> fitted into <strong>c</strong>, since <strong>a</strong> fits into <strong>b</strong>, then <strong>a</strong> would fit into all the <strong>b</strong>'s that fit into <strong>c</strong> and so <strong>a</strong> would have to fit into <strong>c</strong> too.. (think of prime factorisation etc))</p>

<p>this means that we can optimise. If we sort the numbers smallest to largest and start with the smaller numbers first. First iteration, start with the smallest number as <strong>a</strong>
If we partition the numbers into two groups, group <strong>1</strong>, the numbers which <strong>a</strong> divides, and group <strong>2</strong> the group which <strong>a</strong> doesn't divide, then we know that no numbers in group <strong>1</strong> can divide numbers in group <strong>2</strong> because no numbers in group <strong>2</strong> have <strong>a</strong> as a factor.</p>

<p>so if we had [2,3,4,5,6,7], we would start with 2 and get:
[2,4,6] and [3,5,7]
we can repeat the process on each group, splitting into smaller groups. This suggests an algorithm that could count the triples more efficiently. The groups will get really small really quickly, which means its efficiency should be fairly close to the size of the output.</p>

python algorithm