0
\$\begingroup\$

I have some Python code that generates all possible multiples and combinations of a given set of primes up to a certain limit. The code runs and does exactly what I intend it to do, now I am trying to optimize it in order to improve run-time.

import math
from collections import defaultdict
import itertools

lim = 10**13 #This limit can be changed if you'd like
primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47] #So can these primes
res = defaultdict(list)
res[()] = [1] #Maybe not this

for n in range(1, len(primes) + 1):
    for combo in itertools.combinations(primes, n):
        for c in res[combo[:(n - 1)]]:
            stop = int(math.log(lim / c, combo[-1]))
            for x in range(1, stop + 1):
                res[combo[:n]].append(c * combo[-1] ** x)

multiples = []
for key in res:
    multiples += res[key]

multiples.sort()
print(multiples)

If you don't feel like reading through all that, the basic idea is to take increasingly large combinations of the set of primes, starting with a single prime, and computing all the permutations of the subset with increasing powers up to the chosen limit. The way I have it coded, I am initializing the dictionary with an empty tuple that maps to the number 1 as it makes writing the rest of the for loop much easier.

For example: Let's say your list of primes is \$[2,3,5]\$ and your limit is 30. First, it's going to take each number in that list and compute all the powers below 30, storing each in a dictionary key that maps to a list. So, after one loop, you would have:

res = {(): [1], (2):[2,4,8,16], (3):[3,9,27], (5):[5,25]}

The second time through the combinations would be \${2 \choose 3}\$, \${2 \choose 5}\$, and \${3 \choose 5}\$. In each combo, it chops off the last value and searches for the key associated with the remaining part of the tuple. So for \${2 \choose 3}\$ it will look for the (2) key, i.e. the powers of two, and multiply them by increasing powers of three until they go above thirty. So you will have:

\${2 \choose 3}\$ = \$[2 \cdot 3, 2 \cdot 9, 4 \cdot 3, 8 \cdot 3]\$ = \$[6, 18, 12, 24]\$

This process continues until you are out of combinations.

For lower limits the code actually runs fairly quickly. For high limits (\$10^{13}\$, 20 primes) like I have listed above the code runs in about 5 minutes. I would like to get that down to under a minute if possible. I was wondering if I could turn the main for loop into a dictionary comprehension but I'm not sure if that's possible since I've initialized res outside of the main for loop, and need the () = [1] for my code to run.

I am not completely married to this idea, but I do think it's slick (I'm still pretty new to programming so we might have different ideas on what that means), so if I could preserve it that would be nice. Any ideas?

\$\endgroup\$
1

1 Answer 1

3
\$\begingroup\$
  • Give variables better names, exponent is better than x.
  • List comprehensions make your code more understandable.
  • You can use dictionary.values() to get a list of the values.
  • You should make this a function. If you can change; limit, and primes.
  • You're not just getting multiples, you're also getting exponents too. So you may want a better function / variable name.

This can get you:

from collections import defaultdict
from itertools import combinations
from math import log


def prime_multiples(limit, primes):
    res = defaultdict(list)
    res[()] = [1]

    for n in range(1, len(primes) + 1):
        for combo in combinations(primes, n):
            base = combo[-1]
            res[combo] = [
                multiple * base**exponent
                for multiple in res[combo[:-1]]
                for exponent in range(1, int(log(limit / multiple, base)) + 1)
            ]

    multiples = [i for val in key.values() for i in val]
    multiples.sort()
    return multiples


print(prime_multiples(10**13, [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]))

It's 5AM, and I've not tested the following in anyway.
But you could probably change the code to use the modulo operator, %. To check if the number is devisable. And so if you write a generator function, you may be able to use:

def prime_multiples(limit, primes):
    yield 1
    for num in range(1, limit):
        if any(num % prime == 0 for prime in primes):
            yield num
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.