2023 SSMO Accuracy Round Problems/Problem 5

Problem

Define the $\textit{relationship}$ between two numbers $a$ and $b$ to be $\frac{\sigma(ab)}{\sigma(a)\sigma(b)}$ where $\sigma(x)$ is the number of divisors of $x$ . Find the sum of integers $1 \le n \le 100$ which have a relationship of $\frac{3}{4}$ with $360$ .

Solution

Since $360 = 2^3 \cdot 3^2 \cdot 5$ , we have $\sigma(360) = 4 \cdot 3 \cdot 2 = 24$ . For any number $n$ such that $\frac{\sigma(360n)}{24\sigma(n)} = \frac{3}{4}$ , we get $\frac{\sigma(360n)}{\sigma(n)} = 18.$

Let $n = 2^a \cdot 3^b \cdot 5^c \cdot p$ where $\gcd(p, 360) = 1$ . Then the expression becomes $\frac{(a + 4)(b + 3)(c + 2)\sigma(p)}{(a + 1)(b + 1)(c + 1)\sigma(p)} = 18.$

Substituting $d = a + 1$ , $e = b + 1$ , and $f = c + 1$ , we get $\frac{(d + 3)(e + 2)(f + 1)}{def} = 18.$

Try $d = 1$ . Then $\frac{(1 + 3)(e + 2)(f + 1)}{e f} = \frac{4(e + 2)(f + 1)}{ef} = 18 \Rightarrow \frac{(e + 2)(f + 1)}{ef} = \frac{9}{2}.$ Expanding gives $7ef - 2e - 4f - 4 = 0.$

Using Simon's Favorite Factoring Trick, $(7e - 4)(7f - 2) = 36,$ which has a solution of $e = 1$ , $f = 2$ .

So $d = 1$ , $e = 1$ , and $f = 2$ , which means $a = 0$ , $b = 0$ , and $c = 1$ . Therefore, $n = 5p$ for some $p$ relatively prime to 360.

Since $n \leq 100$ , we have $p \leq 20$ . The values of $p$ satisfying this are $1, 7, 11, 13, 17, 19$ . The sum of such integers $n$ is $5 \cdot (1 + 7 + 11 + 13 + 17 + 19) = \boxed{340}.$

~SMO_Team

Page

Toolbox

Search

2023 SSMO Accuracy Round Problems/Problem 5

Problem

Solution