2008 Mock ARML 2 Problems/Problem 2

Problem

Given that the sum of all positive integers with exactly two proper divisors, each of which is less than $30$ , is $2397$ , find the sum of all positive integers with exactly three proper divisors, each of which is less than $30$ (a proper divisor of $n$ is a positive integer that divides but is not equal to $n$ ).

Solution

Let $p,q$ be primes and $r > 1$ . Then we note that $1 | p;\ \boxed{1,p | p^2};\ \boxed{1,p,q | pq};\ \boxed{1,p,p^2 | p^3};\ 1,p,pq,p^2 | p^2q;\ 1,p,q,r,pq,qr,pr | pqr$ . In other words, only perfect squares of primes have exactly two proper divisors (hence $2397 = 2^2 + 3^2 + 5^2 + 7^2 + \cdots + 29^2$ ), and the desired sum consists of all products of two distinct primes and perfect cubes of primes.

The former can be found by using the well-known expansion $(a_1 + a_2 + \cdots + a_n)^2 = a_1^2 + a_2^2 + \cdots + a_n^2 + 2(a_1a_2 + a_1a_3 + \cdots + a_{n-1}a_n)$ , or $(2+3+5 + \cdots + 29)^2 = (2^2 + 3^2 + 5^2 + \cdots + 29^2) + 2(2 \cdot 3 + \cdots + 23 \cdot 29).$ Thus, this sum is $\frac{129^2 - 2397}{2} = 7122$ .

The perfect cubes whose divisors are all less than $30$ are $8, 27, 125$ , and so the answer is $7122 + 8 + 27 + 125 = \boxed{7282}$ .

2008 Mock ARML 2 (Problems, Source)
Preceded by Problem 1	Followed by Problem 3
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8

Page

Toolbox

Search

2008 Mock ARML 2 Problems/Problem 2

Problem

Solution

See also