2005 AMC 10A Problems/Problem 24
Contents
Problem
For each positive integer , let denote the greatest prime factor of . For how many positive integers is it true that both and ?
Solution 1
If , then , where is a prime number.
If , then is a square, but we know that n is .
This means we just have to check for squares of primes, add and look whether the root is a prime number.
We can easily see that the difference between two consecutive square after is greater than or equal to ,
Hence we have to consider only the prime numbers till .
Squaring prime numbers below including we get the following list.
But adding to a number ending with will result in a number ending with , but we know that a perfect square does not end in , so we can eliminate those cases to get the new list.
Adding , we get as the only possible solution. Hence the answer is .
edited by mobius247
Note: Solution 1
Since all primes greater than are odd, we know that the difference between the squares of any two consecutive primes greater than is at least , where p is the smaller of the consecutive primes. For , . This means that the difference between the squares of any two consecutive primes both greater than is greater than , so and can't both be the squares of primes if and . So, we only need to check and .
~apsid
Video Solution
~rudolf1279
Solution 2
If , then , where is a prime number.
If , then , where is a different prime number.
So:
Since : .
Looking at pairs of divisors of , we have several possibilities to solve for and :
(Note: you can skip several cases below by observing that and must be even, and .)
(impossible)
(Valid!)
(impossible)
(impossible)
(not prime)
The only solution where both numbers are primes is .
Therefore the number of positive integers that satisfy both statements is
Solution 3
For the statement to be true, we must have both and be squares of primes. Support we have the number , where is a positive integer. Then the next perfect square, , is greater than . The next perfect square after that will be greater than . In general, the prime will be greater than . However, we must have that . can take on any value between and (if is equal to , we have , where would have to be negative for the difference to be ). However, we can eliminate all the cases where is odd, because we would then have a number of the form , which is odd because can take only integral values. As such, we consider , , and . If , then . Then our squares are and , both of which are squares of primes. If , then . However, isn't prime, so we discard this case. Finally, if , then . Again, isn't prime, so we discard this case as well. Thus, we only have valid case.
~ cxsmi
Video Solution 2
~savannahsolver
Solution 4
We know that since it asks for , we know that must be a perfect square. Plus, we need to be a perfect square of a prime since otherwise won't be equal to the . We can apply the same logic to , and since we also the difference between two consecutive squares is an odd number, we must have an even number of consecutive odd numbers to sum up to since it is even. Thus, this leads us to three cases, since if we split 48 into even more consecutive odd numbers we will go into the negatives:
We know that an odd number, , is equal to the difference of squares between and . This means we can test these cases and find using the least odd number in each case. By looking at the first one, we see that , and squaring it into and setting it to , we realize this works for the first part where is equal to the . Now, if we add we get , which works for the second part. If we do this for the second case, , and square it and set it as , we realize that since must be prime and is composite, so this can't work. Finally for the last case, we do , and since , this case doesn't work since must be greater than . Thus, our only valid case is the first one and our answer is .
~ neeyakkid23
See Also
2005 AMC 10A (Problems • Answer Key • Resources) | ||
Preceded by Problem 23 |
Followed by Problem 25 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 | ||
All AMC 10 Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.