A number has 101 composite factors. How many prime factors at max A number could have ?
A number has 101 composite factors.
-
3If 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? – 2012-06-25
-
2Maximize k for positive integers a_i given ∏(a_i +1) - k = 101 – 2012-06-25
-
3Is 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? – 2012-06-25
-
1exactly 101 composite divisors, and yes the number itself counts. – 2012-06-25
-
2If 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. – 2012-06-25
-
0What will strengthen your concepts is reading what's been written already and trying to understand it. In particular, you have no shot at this question if you don't understand the relation between the prime factorization of a number and the number of factors it has. – 2012-06-25
1 Answers
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.
-
1Not leaving much for OP to do. – 2012-06-25
-
0Yup, I figured it too, thank you. – 2012-06-25
-
2@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... – 2012-06-25
-
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. – 2012-06-25
-
0What 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. – 2012-06-25
-
0I'm sorry sirs. From next time, I'll write my detailed approach from where you can guide me further. – 2012-06-25
-
0Ah ok, I will try to be more considerate of this in future. – 2012-06-25
-
0fretty, you might enjoy reading http://meta.math.stackexchange.com/questions/4300/why-do-some-answerers-prefer-full-solutions-to-hints-for-homework-and-homework-l/4308#4308 – 2012-06-25
-
0Thanks, I certainly agree with what you say and will try to enforce it in future. – 2012-06-25