Skip to main content
OlympiadHQ

Browse · harp

Print

imc

number theory intermediate

Problem

For each positive integer , let denote the greatest prime factor of . For how many positive integers is it true that both and ?
(A)
(B)
(C)
(D)
Solution
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 .
Final answer
B