Prime Generating Integers

Consider the divisors of $30$: $1,2,3,5,6,10,15,30$.
It can be seen that for every divisor $d$ of $30$, $d + 30 / d$ is prime.

Find the sum of all positive integers $n$ not exceeding $100\,000\,000$such that for every divisor $d$ of $n$, $d + n / d$ is prime.

This problem requires both a knowledge of number theory as well as recognising some specific properties of prime numbers.

Consider the divisor pairs $(d, n/d)$ for a positive integer $n$.

Notice that if $n$ is divisible by a divisor $d > \sqrt{n}$, then $n/d < \sqrt{n}$.

We want to find the numbers for which $d + n/d = P$ where $P$ is a prime number.

Since $P = d + n/d > d$, and $d > \sqrt{n}$, we can conclude that $P > \sqrt{n}$.

And since $P = d + n/d < 2d$, we can conclude that $P < 2 \sqrt{n}$.

Therefore, for integer $n$ we only need to consider the primes up to $2 \sqrt{n}$.

Thinking about the restriction $d$ and $n / d$, after considering $n = p^2$ (perfect square form), we realize that in order to satisfy the condition in the problem, $n$ must be either $p^2$ or $2p$, where $p$ is prime.

We will now consider the two cases and find out which values of $p$ lead to valid numbers $n$: 1) If $n = p^2$, for divisors $1$ and $p$, the expression becomes $1 + p^2$ and $p + p$, respectively, and both must be primes.

The first case is satisfied if and only if $p$ is $2$ or $3$ since $4$ and $10$ are the only square numbers plus $1$ that are prime.

The second condition is always met, since the sum of two same primes is always an even integer, which can only be prime if it is $2$. But if $p$ is $2$, the second term would be $4$, which is not prime, so $p$ can only be $3$.

Therefore, $n = 3^2 = 9$ is a valid solution in this case. 2) If $n = 2p$, for divisors $1$, $2$, and $p$, the expressions become $1 + 2p$, $2 + p$ and $p + 2$, respectively.

These are all prime if $p$ is $1$, $3$, $5$ or $11$ (larger primes do not work, as $1 + 2p > 3$ would be an even number greater than $2$, which can’t be a prime). Therefore, we get $n = 2, 6, 10, 22$ as valid solutions for this case.

So, the sum of all numbers up to $100\,000\,000$ not exceeding $100\,000\,000$ with this property (i.e., for every divisor $d$ of $n$, $d + n / d$ is prime) is $9 + 2 + 6 + 10 + 22 = 49$.

More Answers: