Sum of factors algorithm

What is the fastest way to transform a list of prime factors, e.g.

prime_factors = [2, 2, 3] # Prime factors of 12

into the sum of all (regardless of primality) factors:. 1 + 2 + 3 + 4 + 6 + 12 = 28?

I know you can do

sum_factors = 1
for i in set(prime_factors):
     sum_factors = sum_factors*(i**(prime_factors.count(i)+1) - 1)//(i - 1)


from math import prod 

sum_factors = prod((i**(prime_factors.count(i) +1) - 1)//(i - 1) for i in set(prime_factors))

. (The generator expression doesn’t seem that much faster, though.)

Are there more efficient methods?

That’s good. Maybe the counting can be done once, before you begin computing.

from math import prod
from collections import Counter

prime_factors = 10000 * [2,] + 400 * [5,] + 20 * [11,]

count_primes = Counter(prime_factors)

sum_factors = prod(
    (p ** (c + 1) - 1) // (p - 1) for p, c in count_primes.items()

There can’t be since that’s a linear time solution (assuming you gather the counts once).

Remember that asymptotic growth is but one measure notion of efficiency.

This is the expected basic approach - using the formula.

To improve performance, we could generate the counts all at once. The performance impact will probably be negligible in actually difficult cases, though (i.e., the cases where it wouldn’t be super-fast no matter what), because this isn’t saving any time on the actual multiplication, just on setup.

Using .count will have to re-scan the entire list again each time to find the count of each factor. To avoid this, instead of using a set, we can use a data structure that naturally counts the things put into it: collections.Counter. It’s essentially a dictionary where the values correspond to counts (with a bit of extra logic).

from math import prod
from collections import Counter

    (factor**(multiplicity+1) - 1)//(factor - 1)
    for factor, multiplicity in Counter(prime_factors).items()

Optimizing any further would require rather detailed study and benchmarking. For example, one might suppose that division is expensive, so it would be better to compute a separate prod for the numerator and denominator, and do a single division at the end. However, multiplication isn’t constant-time, so this might backfire.

It’s not negligible. It changes a quadratic algorithm into a linear one.

Yes, a single division at the end did a bit better. For

count_primes = {2: 1000000000, 5: 400000, 11: 200}

I got

--- 69.05840849876404 seconds ---
--- 68.92736101150513 seconds ---

Building the long list of primes

prime_factors = 1000000000 * [2,] + 400000 * [5,] + 200 * [11,]

occupies too much memory and the OS kills the script. So, I started from the result of the count directly.

My point is that it probably isn’t optimizing the bottleneck, which (I imagine) is all the multiplications and divisions that will subsequently occur. Suppose for example our list is [2] * 100 + [3] * 100, such that we will end up computing ((2**101 - 1) // 1) * ((3**101 - 1) // 2). However, the numbers have to get really big before that matters, in my testing.

But aside from that, in practical cases it won’t really be quadratic, because numbers with a lot of prime factors typically also have a lot of overlap in those numbers. Prime factors are not equally likely, after all; a given large range of integers contains more even numbers than it does numbers divisible by 3.