python itertools permutations for powers of 2 is too slow

Question

I'm having a very strange issue and can't seem to find a way to fix it.

The following code finds the prime factorisation of n, puts the prime factors into a list then finds all possible sum variations of the prime factors and prints out the unique values of that list.

Example: The prime factors for 44 are 2*2*11 so for 44 it would print out

2,2+2,11,2+11,2+2+11 = 2,4,11,13,15:

Here is my code:

import math
import sys
import itertools
from itertools import permutations

def primes(n):
    primfac = []
    d = 2
    while d*d <= n:
        while (n % d) == 0:
            primfac.append(d)
            n //= d
        d += 1
    if n > 1:
       primfac.append(n)
    return primfac


def primecombo(n):
    b = []
    for i in range(1, len(primes(n))+1):
        for subset in permutations(primes(n), i):
            b.append(sum((subset)))
    a = list(set(b))
    a.sort()
    return a

the code itself seems to work fine and efficiently for the most part but for some very strange reason it becomes ridiculously slow when you're dealing with any number who's only prime factor is 2.

if you try print primecombo(444444) or print primecombo(23452823) it'll print the results almost instantly but if you try 2048 or 4096 it becomes really really slow.

Can anyone see why this is the case and what I can do to fix it?

Answer 1

Short answer

Using itertools.permutations makes your algorithm sum redundant partitions of prime factors. Using itertools.combinations should be a considerable improvement, but we can still do better.

Long answer

Finding all permutations with itertools.permutations makes your function primecombo run in factorial time with regard to the number of factors, worst than exponential.

Let's have a look at the time-complexity with regard to the number of factors k. The dominant step is iterating over permutations(primes(n), len(primes(n)). There are k! permutations and you are suming each of those. The time-complexity of your algorithm is thus

O(k * k!)

That is why 2048, that has 11 factors, is unbearably longer than 23452823, that has 7 factors, to process.

Alternative

Fortunately, visiting every permutation is unnecessary. By example, if you have the factors 2, 3, and 4, you will be summing every permutation of 2, 3 and 4 which is redundant. One quick improvement would be to sum combinations instead, but even then we would sometimes sum the same partition twice when there are factors that appear more than once.

The following solution solves this issue by keeping track of prime factors with a Counter instead of a list. This later allows us to use itertools.product.

This algorithm is able to find the sums you need for 4096 in a matter of milliseconds, see time-complexity analysis below.

import itertools
from collections import Counter

def primes(n):
    primfac = Counter()
    d = 2

    while d ** 2 <= n:
        while (n % d) == 0:
            primfac[d] += 1
            n //= d
        d += 1

    if n > 1:
       primfac[n] += 1

    return primfac

def primecombo(n):
    factor_sums = [[p * e for e in range(exp + 1)] for p, exp in primes(n).items()]

    sums = set(sum(partition) for partition in itertools.product(*factor_sums))

    return sums

primecombo(4096) # {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24}

Time complexity

The time-complexity depends on the distribution of your prime factors. The worst scenario comes if there are k distinct factors. Our itertools.product then has size 2^k. Thus making the algorithm

O(k * 2^k)