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.

A number has 101 composite factors. How many prime factors at max A number could have ?

share|improve this question
3  
If the prime factorization of $n$ is $$n=\prod_{i=1}^kp_i^{a_i}$$ with distinct primes $p_i$ and positive integers $a_i$, how many factors does $n$ have? How many of those are composite? –  Jyrki Lahtonen Jun 25 '12 at 11:50
2  
Maximize k for positive integers a_i given ∏(a_i +1) - k = 101 –  Aang Jun 25 '12 at 11:55
3  
Is the number the product of 101 composite numbers, or does it have exactly 101 composite divisors? In the latter case, does the number itself count? –  Henning Makholm Jun 25 '12 at 12:00
1  
exactly 101 composite divisors, and yes the number itself counts. –  Aang Jun 25 '12 at 12:03
2  
If you need more hints, then how about: for all $i$ we have $a_i+1\ge2$, so $\prod_i(a_i+1)-k\ge 2^k-k$. This is $>101$, iff $k$ is at least __ ? Note: This does not solve the question, but gives you a finite list of possible values of $k$ to check. There is still case-by-case work to do. I leave it at that. –  Jyrki Lahtonen Jun 25 '12 at 12:15

1 Answer 1

up vote 3 down vote accepted

Suppose $m = p_1^{a_1} ... p_n^{a_n}$ has evactly $101$ composite factors.

Then $101 + (1+n) = (a_1 + 1)(a_2+1) ... (a_n+1)$.

But the RHS is at least $2^n$ and it is easily checked that the inequality:

$102 + n \geq 2^n$

fails for $n \geq 7$. So there can be at most $6$ primes in the factorisation of $m$.

We now try to decompose the numbers $101 + (1+n)$ into a product of exactly $n$ integers for $n=1,2,3,4,5,6$, in order to see whether the $a_i$ can actually exist in each case.

We see that:

$108 = 2^2 \times 3^3$

$107$ is prime

$106 = 2\times 53$

meaning that the cases for $n=4,5,6$ cannot work.

However the number $105 = 3\times 5\times 7$ does have such a representation as a product of three numbers. Hence the biggest number of primes you may have in $m$ is $3$ in order to have exactly 101 composite factors.

Such a number is given by $m = p_1^2 p_2^4 p_3^6$ for any three different primes you wish.

As an aside, all such numbers $m$ must be of one of the following forms:

$p_1^2 p_2^4 p_3^6$

$p_1^7 p_2^{12}$

$p_1^3 p_2^{25}$

$p_1 p_2^{51}$

$p_1^{102}$

Where $p_1,p_2,p_3$ are distinct primes.

share|improve this answer
1  
Not leaving much for OP to do. –  Gerry Myerson Jun 25 '12 at 12:28
    
Yup, I figured it too, thank you. –  Bazinga Jun 25 '12 at 12:29
1  
@GerryMyerson: I thought that was the point of this site...to answer questions with detailed explanations (where needed). It seems to me that is what most of the others do... –  fretty Jun 25 '12 at 12:41
1  
@fretty: often, what we do is give the outline of an answer, or ask in the comments for the questioner to develop their ideas, and then once the questioner "gets it" you can expand the answer into a full one. It's usually good to make sure the questioner is meeting you in the middle, as it were. –  Ben Millwood Jun 25 '12 at 12:54
    
What benmachine said. Nothing wrong about writing your answer though. We the teachers at Math.SE like to drop hints first. Of course, the question is fair game while we wait for the OP to get it, so nothing wrong about somebody else writing an answer before that happens. –  Jyrki Lahtonen Jun 25 '12 at 12:58

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.