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?