Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How many ways we can arrange all the prime divisor of a number so it can be written using M factors, where M <=T. T is the total number of prime divisor of the give number N. Example:N=27, its prime divisor is 3(repeating 3 times, so T=3). Now for a given value M=2. There are 2 ways {(3,9),(9,3)}.

The above problem can be solved using brute force approach for small value. I am trying to figure out a generic formula for the above. Please suggest.

share|improve this question
1  
$9$ is not a prime divisor. For $N=11$, there is $T=1$, hence $M\le T$ implies you want only one digit even though $11$ is a two-digit number? –  Hagen von Eitzen Jan 11 '13 at 16:05
    
Do you mean to ask "how many ways can we arrange all the prime divisors of a number so it can be written using M factors? A digit is a numeral $0, 1, ..., 8, 9$. Also, for N = 27, there is only ONE prime divisor, and that being 3. –  amWhy Jan 11 '13 at 16:05
    
Perhaps your question is : How many ways can a number $N$ be written as product of $M$ numbers. Or $M$ factors larger than 1. (And I suppose order of factors counts). –  Maesumi Jan 11 '13 at 16:09
    
@amWhy,Maesumi:yeah u guys are getting it right...I have modified the question accordingly. –  rspr Jan 11 '13 at 17:21
    
For your example of $27$, what about $(1,27)$ and $(27,1)$? Do they count? It gets easier then. –  Ross Millikan Jan 11 '13 at 17:25

1 Answer 1

up vote 2 down vote accepted

If you number is $N$, you can express it as a product of primes to exponents, $N=p_1^{e_1}p_2^{e_2}\ldots p_n^{e_n}$. The first thing to notice is that you don't care about the $p_i$, the number of ways will only depend upon the $e_i$

Now you can think about your factors being $M$ buckets that you put the prime factors into, multiplying all the prime factors in each bucket. The powers of $p_1$ can be distributed in the number of compositions of $e_1+M$ into $M$ parts. Each part is at least $1$ and you put one less than the part into the particular bin. For example, with $e_1=4, M=3$, you can have $7=5+1+1, 4+2+1, 3+2+2, $ and many others. These would correspond to numbers of factors of $p_1$ split $(4,0,0), (3,1,0), (2,1,1), $ and so on. The article shows that the number of compositions is then ${e_1+M-1} \choose {M-1}$. You then multiply all of these terms for each prime, so the total number is $$\prod_i {{e_i+M-1} \choose {M-1}}$$

This will include cases where one or more of the factors is $1$ because a bucket didn't get any factors at all. It is harder to count those because it makes interactions between the various primes.

share|improve this answer
    
explained well....but if there is restriction that each bucket will hold at least one prime factor F>1.How do u suggest to handle it. –  rspr Jan 12 '13 at 6:39
    
@rspr: I would sum over the number of empty buckets. For one bucket empty, there are M choices for which will be empty, then the same function with M-1 buckets for how to fill the rest. For two empty, there are M(M-1)/2 ways to choose the empties, then the same function with M-2 buckets to fill the rest. –  Ross Millikan Jan 12 '13 at 16:09

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.