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.

Answer 2

Here's a solution using a generator (and itertools.count):

from itertools import count

def products(numbers, limit):
    numbers = set(numbers)  # needs a set to pop from, not a tuple
    while numbers:
        n = numbers.pop()
        for r in (n ** e for e in count(1)):
            if r > limit:
                break
            yield r
            for p in products(numbers, limit / r):
                yield r * p

Since it is a generator, it returns an iterator - and the results aren't sorted, so for the specific output you want, you'd call it like this:

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

Answer 3

The idea to use only itertools with tuple (2,3,4) for example:

Have multiple cartesian products:

(2,),(3,),(4,) # repeat 1
(2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4), (4, 2), (4, 3), (4, 4) # repeat 2
...

For each of this tuple, use reduce with operator.mul and starting value 1, to multiply them:

reduce(operator.mul, tuple, 1)

This will yield the multiplications for level 2 cartesian's product:

[reduce(operator.mul,t,3) for t in itertools.product((1,2,3),repeat=2)]
>>>[3, 6, 9, 6, 12, 18, 9, 18, 27]

Now, we need to increase repeat until a stop condition is met, say: every multiplication will yield a result larger than the top. Since the samllest value that counts is 2 (because 1 times 1 many times is just 1 so it wont count) we can multiply 2 times x while is lower than top. So: top/2 = x, means that we can iterate through range(1,top/2):

[reduce(operator.mul,t,1) for c in range(1,10/2) for t in itertools.product((1,2,3),repeat=2) if reduce(operator.mul, t, 1) < 10]

This will yield repeated values, so let's convert them in a set:

set([reduce(operator.mul,t,1) for c in range(1,10/2) for t in itertools.product((1,2,3),repeat=2) if reduce(operator.mul, t, 1) < 10])

Using only itertools may be cumbersome for this, but the solution seems pretty. I'm sure it can be optimized by introducing a better stop condition. The final code would look like this:

NOTE: There's a theorem for prime numbers that will allow you to optimize the stop condition to math.sqrt(top)

import math
def f(t,m):
    return set([reduce(operator.mul, t1, 1) for c in range(1,int(math.sqrt(m)) for t1 in itertools.product(t,repeat=c) if reduce(operator.mul,t1,1) < m])

f((2,3,4),10)
>>>set([2, 3, 4, 6, 8, 9])

Hope this might give you another idea :)