non-prime factorings with some repeats
Question: Let's say we have numbers factors, for example 1260:

    
    
    >>> factors(1260)
    [2, 2, 3, 3, 5, 7]
    

Which would be best way to do in Python combinations with every subproduct
possible from these numbers, ie all factorings, not only prime factoring, with
**sum of factors** less than **max_product**?

If I do combinations from the prime factors, I have to refactor remaining part
of the product as I do not know the remaining part not in combination.

I can also refine my **divisors** function to produce pairs of divisors
instead of divisors in size order, but still it will cost me to do this for
number with **product upto 12000**. The product must remain always the same.

I was linked to divisor routine, but it did not look worth the effort to prove
them to adopt to my other code. At least my divisor function is noticably
faster than sympy one:

    
    
    def divides(number):
        if number<2:
            yield number
            return
        high = [number]
        sqr = int(number ** 0.5)
        limit = sqr+(sqr*sqr != number)
        yield 1
        for divisor in xrange(3, limit, 2) if (number & 1) else xrange(2, limit):
            if not number % divisor:
                yield divisor
                high.append(number//divisor)
        if sqr*sqr== number: yield sqr
        for divisor in reversed(high):
            yield divisor
    

Only problem to reuse this code is to link the divisors to factoring sieve or
do some kind of itertools.product of divisors of the divisors in pairs, which
I would give out as pairs instead of sorting to order.

Example results would be:

    
    
    [4, 3, 3, 5, 7] (one replacement of two)
    [5, 7, 36] (one replacement of three)
    [3, 6, 14, 5] (two replacements)
    

Probably I would need some way to produce sieve or dynamic programming
solutions for smaller divisors which could be linked to numbers whose divisors
they are. Looks difficult to avoid overlap though. I do have one sieve
function ready which stores biggest prime factor for each number for speeding
up the factoring without saving complete factorings of every number... maybe
it could be adapted.

**UPDATE: The sum of factors should be near the product, so probably there is
high number of factors of <= 10 in answer (upto 14 factors).**

**UPDATE2:** Here is my code, but must figure out how to do multiple removals
recursively or iteratively for parts > 2 long and dig up the lexical
partitioning to replace the jumping bit patterns which produce duplicates
(pathetic hit count only for one replacement, and that does not count the
passing of 'single element partionings' inside the single_partition):

    
    
    from __future__ import print_function
    import itertools
    import operator
    from euler import factors
    
    def subset(seq, mask):
        """ binary mask of len(seq) bits, return generator for the sequence """
        # this is not lexical order, replace with lexical order masked passing duplicates
        return (c for ind,c in enumerate(seq) if mask & (1<<ind))
    
    
    def single_partition(seq, n = 0, func = lambda x: x):
        ''' map given function to one partition  '''
        for n in range(n, (2**len(seq))):
            result = tuple(subset(seq,n))
            others = tuple(subset(seq,~n))
            if len(result) < 2 or len(others) == 0:
                #empty subset or only one or all
                continue
            result = (func(result),)+others
            yield result
    
    
    if __name__=='__main__':
        seen,  hits, count = set(), 0, 0
        for f in single_partition(factors(13824), func = lambda x: reduce(operator.mul, x)):
            if f not in seen:
                print(f,end=' ')
                seen.add(f)
            else:
                hits += 1
            count += 1
        print('\nGenerated %i, hits %i' %(count,hits))
    

**REFINEMENT** I am happy to get only the factorings with max 5 factors in the
non-prime factor parts. I have found by hand that non-decreasing arrangements
for up to 5 same factors follow this form:

    
    
    partitions of 5    applied to 2**5
    1  1  1   1  1     2  2   2   2  2
    1  1  1     2      2  2   2    4
    1  1  1  3         2  2      8
    1   2       2      2    4      4 
    1       4          2      16
      2      3           4       8
    

**THE SOLUTION** I do not remove the accepted answer from fine solution down,
but it is over complicated for the job. From Project Euler I reveal only this
helper function from orbifold of NZ, it works faster and without needing the
prime factors first:

    
    
    def factorings(n,k=2):
        result = []
        while k*k <= n:
            if n%k == 0:
                result.extend([[k]+f for f in factorings(n/k,k)])
            k += 1
        return result + [[n]]
    

The relevant **solution for problem 88** of his run in Python 2.7 in 4.85 s by
my timing decorator and after optimizing the stop condition by found counter
**3.4 s in 2.6.6 with psyco** , 3.7 s in 2.7 without psyco . Speed of **my own
code** went from 30 seconds with code in accepted answer (sorting added by me
removed) to 2.25 s (2.7 without psyco) and **782 ms with psyco in Python
2.6.6.**


Answer: What you are looking for is more commonly called a **divisor**. This answers
to [this question](http://stackoverflow.com/questions/171765/what-is-the-best-
way-to-get-all-the-divisors-of-a-number) may help you.

