A Divisor Diversion

The only positive integers that have precisely $3$ positive divisors are squares of primes $p$ , (the $3$ divisors being $1, p$ and $p^{2}$ ). So we are looking for positive integers $n$ that equal $p^{2} - 1$ for some prime $p$ and have a total of $16$ positive divisors.

For $p = 2$ we have $p^{2} - 1 = 3$ which has only $2$ divisors, and for $p = 3$ we have $p^{2} - 1 = 8 = 2^{3}$ , which has only $4$ divisors. Now all primes $p \gt 3$ are of the form $6k \pm 1$ for some positive integer $k$ . Then $p^{2} - 1 = (6k \pm 1)^{2} - 1 = 36k^{2} \pm 12k = 12k(3k \pm 1)$ . Now if $k$ is even then $24 | 12k$ and if $k$ is odd then $3k \pm 1$ is even and so $24 | 12(3k \pm 1)$ . Either way we have that $24 | p^{2} - 1$ . Now $24 = 2^{3} \times 3$ has $(3 + 1)(1 + 1) = 8$ divisors, so for $p^{2} - 1$ to end up with a total of $16$ divisors we can introduce precisely one of the factors $2^{4}, 3^{2}$ or a prime (to the power $1$ ) other than $2$ or $3$ .

Now since $p^{2} = (p - 1)(p + 1)$ , and $p - 1$ and $p + 1$ differ by $2$ , if the added factor were:

• (i) $2^{4}$ then we would need to be able to write $2^{7} \times 3$ as a product of two integers that differ by $2$ . The closest we can get in this case is $16 \times 24$ ;

• (ii) $3^{2}$ then we would need to be able to write $2^{3} \times 3^{3}$ as a product of two integers that differ by $2$ . The closest we can get in this case is $12 \times 18$ .

So we are left with the added prime option to look at. Now one of $p - 1$ or $p + 1$ will be divisible by at least $6$ and the other by at least $2$ , and since they are successive even numbers one will also be divisible by $4$ . So say one is divisible by $12$ and the other by $2$ . Then for $p - 1$ and $p + 1$ to differ by $2$ the introduced prime must be either $5$ or $7$ , yielding $2 \times 5 = 10$ along with $12$ as one pair, and $2 \times 7 = 14$ along with $12$ as another pair. If one was divisible by $6$ and the other by $4$ then only by introducing the factor $2$ could we get successive even numbers $6$ and $2 \times 4 = 8$ , but the prime we need to introduce must be other than $2$ or $3$ .

So after looking at all the cases, the only positive integers $n$ that satisfy the conditions are

$10 \times 12 = 2^{3} \times 3 \times 5 = 120 = 11^{2} - 1$ and $12 \times 14 = 2^{3} \times 3 \times 7 = 168 = 13^{2} - 1$ ,

the sum of which is $120 + 168 = \boxed{288}$ .

A slightly different presentation...

We want $\sigma_0(n) = 16$ and $\sigma_0(n+1) = 3$ . The second of these tells us that $n = p^2 - 1$ where $p$ is prime. Since $n=3$ is not a solution to the problem, $p$ must be odd. Thus both $p-1,p+1$ are even, and exactly one of them is a multiple of $4$ . Thus we can write $p\pm1 \; = \; 2^{a}q \hspace{2cm} p \mp1 \; = \; 2r$ where $a \ge 2$ and $p,q$ are coprime odd integers. Thus $n = p^2-1 = 2^{a+1}qr$ and so $16 = \sigma_0(n) = (a+2)\sigma_0(q)\sigma_0(r)$ . Since $a+2 \ge 4$ , there are three options:

1. If $a+2 = 16$ , then $a=14$ and $q=r=1$ . But then $p \pm1 = 2^{14}$ , $p \mp1 = 2$ , which is impossible.

2. If $a+2 = 8$ , then $a=6$ and $\sigma_0(q)\sigma_0(r) = 2$ . Now $n=8$ is not a solution, so $p=3$ is not allowed, and hence $r$ cannot be equal to $1$ . Thus $r$ must be prime, and $q=1$ . But then $p = 2^6 \pm 1$ is either $63$ or $65$ , which is impossible.

3. if $a+2 = 4$ , then $a=2$ and $\sigma_0(q)\sigma_0(r) = 4$ . If $q=1$ then $p = 3,5$ , and so $n = 8,24$ , neither of which are possible. If $r=1$ then $p = 3$ , which is impossible. Thus we deduce that both $q$ and $r$ are prime.

This last case now breaks down into two final subcases:

• If $p = 4q + 1 = 2r - 1$ , then $r = 2q+1$ . If $q \equiv 1 \pmod{3}$ , then $r \equiv 0 \pmod{3}$ , so that $r=3$ and $q=1$ , which is impossible. If $q \equiv 2 \pmod{3}$ then $p \equiv 0 \pmod{3}$ , and hence $p=3$ , which is impossible. Thus $q \equiv 0 \pmod{3}$ , and hence $q=3$ , so that $p=13$ , $r=7$ , and hence $n=168$ is one solution.

• If $p = 4q-1 = 2r+1$ , then $r = 2q-1$ . If $q \equiv 1 \pmod{3}$ , then $p \equiv 0 \pmod{3}$ , so that $p=3$ , which is impossible. If $q \equiv 2 \pmod{3}$ then $r \equiv 0 \pmod{3}$ , and hence $r=3$ , so that $q=2$ , which is impossible. Thus $q \equiv 0 \pmod{3}$ , and hence $q=3$ , so that $p=11$ , $r=7$ , and hence $n=120$ is the other solution.

Thus the answer is $168 + 120 = \boxed{288}$ .