Question

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$ is $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}\}?$

the set of positive integers

the set of composite positive integers

the set of even positive integers

the set of integers greater than $3$

the set of integers greater than $4$

Answer: D

Concepts:prime factorization function

Difficulty rating: 1970

Small Hint:

The smallest value comes from the smallest composite, $4 = 2 \cdot 2$

Big Hint:

Show every integer greater than $3$ is attained, e.g. $r(2^k) = 2k$ and $r(2^k\cdot 3) = 2k + 3$

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.

2015 AMC 12B Problem 18

Answer: D

Difficulty rating: 1970

Small Hint:

Big Hint:

Solution:

Problem 18 in Other Years