Maths Olympiad Prep

Library / /1078 of 1394

Number theory Difficulty 5.6 AIME, harder Prove it United States

Problem:
A positive integer nn is loose if it has six positive divisors and satisfies the property that any two positive divisors a<ba < b of nn satisfy b2ab \geq 2a. Compute the sum of all loose positive integers less than 100100.

Solution

Solution:
Note that the condition in the problem implies that for any divisor dd of nn, if dd is odd then all other divisors of nn cannot lie in the interval [d2,2d1]\left[\left\lceil\frac{d}{2}\right\rceil, 2d-1\right]. If dd is even, then all other divisors cannot lie in the interval [d2+1,2d1]\left[\frac{d}{2}+1, 2d-1\right].

We first find that nn must be of the form p5p^{5} or p2qp^{2}q for primes pp and qq. If n=p5n = p^{5}, the only solution is when p=2p = 2 and n=32n = 32.

Otherwise, n=p2qn = p^{2}q. Since 100>n>p2100 > n > p^{2}, so p7p \leq 7. Now we can do casework on pp.

When p=2p = 2, we find that qq cannot lie in [2,3][2,3] or [3,7][3,7], so we must have q11q \geq 11. All such values for qq work, giving solutions n=44,52,68,76,92n = 44, 52, 68, 76, 92.

When p=3p = 3, we find that qq cannot lie in [2,5][2,5] or [5,17][5,17], so we must have that q19q \geq 19, so there are no solutions in this case.

When p=5p = 5 or p=7p = 7, the only solution occurs when q=2q = 2 (since otherwise n>100n > 100). This gives us the solutions n=50n = 50 and n=98n = 98.

Adding these values of nn gives 32+44+52+68+76+92+50+98=51232 + 44 + 52 + 68 + 76 + 92 + 50 + 98 = 512.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.