Enumeration of all factor products less than a maximum

Question

I want to enumerate all possible products of some integer factors, only up to some maximum value:

• P((2, 3, 11), 10) would return (2, 3, 4, 6, 8, 9).
• P((5, 7, 13), 30) would return (5, 7, 13, 25).

This seems like a tree traversal where the branches stop growing once reaching the maximum, but I don't know what the bound is on the number of branches. What algorithm or idiom is recommended for this problem? the closest thing I have seen so far is itertools.product(), which seems to set a fixed number of terms per output set (e.g. 2).

For context, I am trying to inspect the numbers that are coprime to n. in this case n itself is the upper limit and the list of factors are those of n. I tried to generalize the question a bit above.

Answer 1

I like this method, which involves multiplying 1 by all the elements in the input list, then multiplying all the results by the elements in the input list, etc. until the limit is reached.

def signature_seq(signature, limit):
  products = set((1,))
  for factor in signature:
    new_products = set()
    for prod in products:
      x = factor * prod
      while x <= limit:
        new_products.add(x)
        x *= factor
    products.update(new_products)

  products.remove(1)
  return products

This should do what you want:

>>> print(sorted(signature_seq((2, 3, 11), 10)))
[2, 3, 4, 6, 8, 9]
>>> print(sorted(signature_seq((5, 7, 13), 30)))
[5, 7, 13, 25]

By the way, if given a list of consecutive primes starting with 2, this is a smooth number generator.