2008 Mock ARML 2 Problems/Problem 2

Revision as of 18:58, 29 May 2008 by Azjps (talk | contribs) (solution)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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}$.

See also

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