<p>If n = (a^2)bc where a b and c are each different prime numbers greater than 2, how many integers greater than 2 and less than n are divisors of n? </p>
<p>I have assumed the numbers 3, 5, and 7, but I need a way to find the exact number of factors. Better yet, I am looking for a way Without assuming numbers.</p>
<p>Difficulty level: 5</p>
<p>I have assumed the numbers 3, 5, and 7, but I need a way to find the exact number of factors. Better yet, I am looking for a way Without assuming numbers.</p>
<p>Now that you have this number, N= 3x3x5x7, look at how you can construct its factors:</p>
<p>3
5
7
3x3
3x5
3x7
5x7
3x3x5
3x3x7
3x5x7</p>
<p>3x3x5x7 is a factor too, but they want factors less than n.</p>
<p>You could have made this list using the letters instead of the numbers. I can’t think of an approach that is faster than listing…</p>
<p>In general we have:</p>
<p>a, b, c, ab, ac, bc,
a^2, a^2<em>b, a^2</em>c, abc</p>
<p>Even more generally, if you have a prime factorization of a positive integer, then you can get the total number of factors by multiplying one more than each exponent together in the prime factorization. In this example, since the powers are 2, 1, and 1, we get 3<em>2</em>2 = 12. But the question doesn’t want 1 or the number itself. So there are 12 - 2 = 10.</p>
<p>As another example, the number of factors of a^3<em>b^2</em>c<em>d^4 where a, b, c, and d are prime is 4</em>3<em>2</em>5 = 120.</p>
<p>I’m pretty sure that this is correct, but I did just derive this little formula on the spot, so feel free to correct me if there is an error.</p>
<p>^Nice Nice Nice!</p>
<p>And it uses the counting principle! You are considering each factor and deciding how many of them to include in your new product. You can choose anywhere from zero up to the number of each factor there are (which is why you add one to each exponent). Very cool approach. I would never have thought of this as fast as listing! </p>
<p>Yeah, 10 is correct. When the problem asks “how many factors…” I would almost never list them out.</p>
<p>Similarly, if a problem asks for the sum of the positive factors of a number n, you can also evaluate the sum pretty easily without listing if you have the prime factorization.</p>
<p>As a rule, I believe I can apply what you just did drsteve, but I honestly don’t understand what pckeller is talking about and I feel like I am missing something important.</p>
<p>I meant to explain the reasoning behind DrSteve’s formula – can we name it that? As he said, suppose you have the prime factorization of a number…let’s say it’s:
(a^x)(b^y)(c^z)(d^w)</p>
<p>And now you want to know how many factors the number has. DrSteve’s formula says just multiply:
(x+1)(y+1)(z+1)(w+1) – you have multiplied one more than each exponent. I had never seen that before and I was trying to explain why it works.</p>
<p>Say you were going to build a factor of the original number from scratch. You would only be able to use its prime factors and you could only use up to as many of each factor as there was in the original number. But you could also choose to leave out any particular prime factor entirely, choosing to include 0 of them. So one factor at a time, you have to make a decision: how many factors should I choose to include? You have one more choice than the exponent of that factor because you could also choose zero. Then, as the counting principle says, to find the total number of ways, you multiply the individual numbers of choices.</p>
<p>Is this important? Well, it is INTERESTING. I’ve always really liked combinatorics. And the counting principle is definitely tested on the SAT. But as soon as it gets too subtle, listing and counting becomes the safer plan. That’s why you don’t need to know about nPr vs. nCr. I just found this to be an interesting problem and DrSteve’s solution is elegant.</p>
<p>Here is another example problem:
Q: How many positive factors of 900 are even?</p>
<p>One could list them out, but that is horribly inefficient. Instead, we note that 900 = 30^2 = (2^2)(3^2)(5^2). Any such even factor of 900 will be of the form (2^x)(3^y)(5^z) where x >= 1. So x can be 1 or 2, and y and z can be 0, 1, or 2, so the number of even factors is 2<em>3</em>3 = 18.</p>
<p>For a bit more of a challenge, try this one:</p>
<p>Given a list of 50 positive integers, each no bigger than 98, show that at least one integer in the list is divisible by another integer in the list.</p>
<p>^ Just proved it using pigeonhole.</p>
<p>Yep - pigeonhole principle is the way to go. Let’s see if anyone can write out the details.</p>
<p>I can but I’ll wait a bit for anyone else who wants to solve it.</p>
<p>Well, here’s my solution.</p>
<p>Assume the 50 integers are distinct (otherwise two integers are equal and divisible by each other). Partition {1,2,…,98} into sets as follows:</p>
<p>S<em>1 = {1,2,4,…,64}
S</em>2 = {3,6,12,…,96}
S<em>3 = {5,10, …,80}
…
S</em>49 = {97}</p>
<p>i.e. S<em>i is the set of integers in {1,2,…,98} whose largest odd divisor is 2i-1. By pigeonhole, two of the numbers in our list of 50 are contained in the same S</em>i. The larger one divided by the smaller one is a power of 2, done.</p>
<p>@MITer Perfect! </p>
<p>Just to summarize (without all of the notation), since there are only 98/2 = 49 odd integers less than 98, there must be 2 integers in our list of 50 with the same “odd part.” In other words these two integers have the form m<em>2^a and m</em>2^b where m is an odd integer. If a < b, then m<em>2^a divides m</em>2^b.</p>
<p>
</p>
<p>How about: all positive even integers greater than 2 are divisible by 2. So, if we have 50 integers less than 98 we can have one even integer and the remaining integers must be odd - and that will include all odd positive integers less than 98 (98 / 2 = 49). All odd positive integers less than 98 include 9 and 3 and 9 is divisible by 3. I’m not sure if this proves it to anyone else, but I’ve convinced myself. :)</p>
<p>@CHD2013 yeah, that’s not a valid proof…to prove it you have to show that regardless of your choice of integers, there will be two such that one divides the other. Maybe we don’t choose 3. Or maybe we choose {49, 50, …, 98} in which the <em>only</em> pair of integers such that one divides the other is {49, 98}.</p>
<p>^Thanks. I think your analysis can be helpful even if a formal proof is unnecessary.</p>
<p>@CHD what about 5, 7, 11, 13, 17,…</p>
<p>There are infinitely many primes. 3 is just one of these primes. So there are many numbers less than 98 that are not divisible by 3.</p>
<p>Here’s a similar pigeonhole-type problem:</p>
<p>Prove that in the sequence pi, 2pi, 3pi, 4pi, …, one of the terms gets arbitrarily close to an integer.</p>