Product of prime factors of a number, less than that number

Question

First of all, I apologise for the title, I did not know how to put my problem in words. Well, here it is:

For an integer a greater than 1, let F be a sorted list of prime factors of a. I need to find all tuples c (filled with whole numbers), such that length of each tuple is equal to the size of F and (F[0] ** c[0]) * (F[1] ** c[1]) * (...) < a. I should add that I write in Python.

Example:

a = 60
F = [2,3,5]

# expected result:

C = {(0, 0, 0), (0, 0, 1), (0, 0, 2), (0, 1, 0), (0, 1, 1), (0, 2, 0),
(0, 2, 1), (0, 3, 0), (1, 0, 0), (1, 0, 1), (1, 0, 2), (1, 1, 0), (1, 1, 1),
(1, 2, 0), (1, 3, 0), (2, 0, 0), (2, 0, 1), (2, 1, 0), (2, 2, 0), (3, 0, 0),
(3, 0, 1), (3, 1, 0), (4, 0, 0), (4, 1, 0), (5, 0, 0)}

I generated this result using itertools.product(), specifically:

m = math.floor(round(math.log(a, min(F)), 12))
for i in itertools.product(range(m + 1), repeat=len(F)):
    if math.prod([F[j] ** i[j] for j in range(len(F))]) < a: print(i)

I think it works but it's inefficient. For example number 5 appears only in one tuple, but was checked many more times! Is there any way to make it faster? I would use multiple while loops (with break statements) but since I don't know what is the length of F, I don't think that is possible.

Answer 1

You base all your range limits on just min(F). Let's customize each to the log(a, factor) to reduce the cases:

from math import ceil, log, prod
from itertools import product

a = 60
F = [2, 3, 5]

ranges = [range(0, ceil(log(a, factor))) for factor in F]

C = []

for powers in product(*ranges):
    if prod(F[i] ** power for i, power in enumerate(powers)) < a:
        C.append(powers)

print(C)

By my measure, your code generates 216 test cases to come up with 25 results, but the above code only generates 1/3 of those test cases.