CODEWITHSUNDEEP
pythonpython-2.7list-comprehensionprimesprime-factoring
NNN
NNN

Reputation: 135

Python product of arbitrary number of variables

EDIT: Though I did say in the original post that I'd like to use list comprehension, I would gladly accept any solution. I simply assumed list comprehension would be the simplest way to do it.

I am working on a problem involving prime factorization, and have run into an issue regarding list comprehension.

I have a list of prime factors of a number, and of course the list could be any number of numbers. It could be [2,3,5] or just [2], or [2,3,11,17], etc.

What I would like to be able to do would be to find all products of powers of these numbers such that the product is less than or equal to 100,000. So for example if my prime factorization is [2,3,5], I would like to have all numbers of the form (2^a)(3^b)(5^c) for natural numbers a,b,c, satisfying (2^a)(3^b)(5^c) <= 100,000.

Is there a way to do this with list comprehension given that the number of prime factors is an arbitrary length?

Upvotes: 0

Views: 343

Answers (3)

TurtleIzzy
TurtleIzzy

Reputation: 1047

Check this out.

import math

Nmax = 100
primeLst = [2, 3, 5]


result = []
enumMax = [int(math.floor(math.log(Nmax) / math.log(i))) for i in primeLst]

def prod(i, curRes):
    if curRes > Nmax:
        return
    if i==len(primeLst):
        result.append(curRes)
    else:
        for j in range(enumMax[i]+1):
            prod(i+1, curRes * (primeLst[i]**j))

prod(0, 1)

# result: [1, 5, 25, 3, 15, 75, 9, 45, 27, 81, 2, 10, 50, 6, 30, 18, 90, 54, 4, 20, 100, 12, 60, 36, 8, 40, 24, 72, 16, 80, 48, 32, 96, 64]

Upvotes: 0

Dan D.
Dan D.

Reputation: 74655

This modification of @niemmi's answer uses heapq.merge to merge each of the sequences from each of the recursive calls to produce the products in increasing order:

from heapq import merge

def prods(factors, limit, index = 0, total = 1):
    # Base case, yield current number
    if index >= len(factors):
        yield total
        return
    iters = []
    while total < limit:
        iters.append(prods(factors, limit, index + 1, total))
        total *= factors[index]
    for res in merge(*iters):
        yield res

print list(prods([2, 3, 5], 100))

There is the output:

>>> print list(prods([2, 3, 5], 100))
[1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, 40, 45, 48, 50, 54, 60, 64, 72, 75, 80, 81, 90, 96]

Upvotes: 0

niemmi
niemmi

Reputation: 17263

You could use recursive function that picks one of the factors and multiplies the current total until the total is above the limit. For each iteration you could then recursively call the same function while moving to next factor. Once you have exhausted all the factors just yield the current total:

def prods(factors, limit, index = 0, total = 1):
    # Base case, yield current number
    if index >= len(factors):
        yield total
        return

    while total <= limit:
        # Python 3 yield from could be used
        for res in prods(factors, limit, index + 1, total):
            yield res
        total *= factors[index]

print list(prods([2, 3, 5], 100))

Output:

[1, 5, 25, 3, 15, 75, 9, 45, 27, 81, 2, 10, 50, 6, 30, 18, 90, 54, 4, 20, 100, 12, 60, 36, 8, 40, 24, 72, 16, 80, 48, 32, 96, 64]

Upvotes: 1

Related Questions