2015 AMC 12B Problem 18

Problem 18 of 25IntermediateAlgebra Number Theory

For every composite positive integer

n,

define

r(n)

to be the sum of the factors in the prime factorization of

n.

For example,

r(50) = 12

because the prime factorization of

50

2 \cdot 5^2,

and

2 + 5 + 5 = 12.

What is the range of the function

r,

\{r(n) : n \text{ is a composite positive integer}\}?

Show solution

Solution

A composite number has at least two prime factors (with multiplicity), and the smallest prime is

2,

so the least possible value is

2 + 2 = 4.

Every integer greater than

3

is attained:

r(2^k) = 2k

covers the even values

\ge 4,

and

r(2^k\cdot 3) = 2k + 3

covers the odd values

\ge 5.

So the range is the integers greater than

3.

Thus, the correct answer is D.