Count possible combinations of factors of number N, excluding 1 and itself, which on multiplication yield N

Eeshan 0
Viewed 54

Given a number N, find the number of combinations of its factors (excluding 1 and N), which on multiplication yield N. Eg:

N = 12
answer = 3
relevant factors : 2,3,4,6
combinations : {2,6},{3,4},{2,2,3}.

To solve this, I came up with the following logic, which is adequate for nearly all cases, but undercounts in a few cases. Please help me in understanding what I am missing. My Logic:

I divide the set of combinations into "primary" and "secondary". The ones which occur as a direct combination of the factors are primary. In the above example, {2,6} and {3,4} are primary. Those which come up as a result of further breaking one of the original factors is secondary. Eg: {2,2,3} can be called a combination of 2 with breakdown of 6 into {2,3} or of 3 with breakdown of 4 into {2,2}. For every number, I first find the number of primary factors, then the number of secondary factors by recursively repeating the process for the largest relevant factor. Eg:

f(32) = 2 + f(16);
f(16) = 2 + f(8);
f(8) = 1 + f(4);
f(4) = 1;
Thus, f(32) = 6.

In the above, the primary combinations of 32 are {2,16} and {4,8}. Hence the 2 in the first step. This explains rest of the steps too.

The problem is, this solution fails for a few values of N. Eg: It returns 8 for 90, but the correct answer is 10. It returns 16 for 180, but the correct answer is 25. For 60, correct is 10, but mine is 9.

Please help me.

number-theory math recursion algorithm
2 Answers

Using the guidance from the comment from @kcsquared, I was able to understand how exactly to approach this problem.

We simply need to iterate over all divisors of n. Doing so will give what I was referring in the question as "primary combos". In order to find multiplicative partitions using recursion, I should recursively find divisors of the larger of the two divisors found in the ongoing iteration, but this time with a modification. Rather than starting search from 2, one should start from the smaller divisor from the iteration. This is to prevent over-counting. Below is my code.

def divisors(s,l):
    tot = 0
    for i in range(s,l):
        if n%i == 0 and n//i >= i: #Preventing counting same combo again, and early stopping.
            tot += 1
            if n//i > 0:
                tot += divisors(i,n//i)
    return tot
n = 60
print(divisors(2,n))

This is giving the correct answer. The implementation I came up with earlier was much more complex, and was unable to recurse for anything but the largest factor. If I do that for n = 60, I will not be able to count {3,4,5}, as:

On partitioning 60, I get: 2,3,4,5,6,10,12,15,20,30.

Now, If I further divide 30, then 15 then 5, I will not get 4 anywhere, since 4 is not a factor of any of these. Hence, 4 will only be counted once in the first step, as part of {4,15}, but never as {3,4,5}.

With the new approach, I will also be able to divide 20 (20*3 = 60), which will count the occurrence of 3 along with 4 and 5.

Eeshan0

I would do a prime factorization of N first and then compute the number (probably using combinatorics) from the exponents (above 1) of primes ...

For example:

x^1                                       // 1 options
x^2 = x*x                                 // 2 options
x^3 = x^2*x = x*x*x                       // 3 options
x^4 = x^3*x = x^2*x^2 = x^2*x*x = x*x*x*x // 5 options
x^5 = x^4*x = x^3*x^2 = x^3*x*x*
    = x^2*x^2*x = x^2*x*x*x = x*x*x*x*x   // 7 options
x^6 = x^5*x = x^4*x^2 = x^4*x*x
    = x^3*x^3 = x^3*x^2*x = x^3*x*x*x
    = x^2*x^2*x^2 = x^2*x^2*x*x
    = x^2*x*x*x*x = x*x*x*x*x*x           // 11 options
...

2^2 * 3^1 = 12
options:      2  +  1  = 3 
combinations: 3: {2,6},{3,4},{2,2,3}

2^2 * 3^1 * 5^1 = 60
options:      2  +  1  +  1 = 4 options
combinations: 9: {12,5},{2,6,5},{3,4,5},{2,2,3,5},{6,10},{3,20},{2,2,15},{4,15},{2,30}

However I am not sure what the formulas are for options = f(exponent) and combinations = f(sum_of_options) it most certainly involves combinatorics and or recursive calculations from one less exponent. I am too lazy to check it for now...

Spektre0
Related