When all of $n-2$, $n+2$, $n^2-2$, and $n^2+2$ are primes?

Question

Find the smallest $5$-digit number $n$ for which all of numbers $n-2$, $n+2$, $n^2-2$, and $n^2+2$ are primes.

Actually after some calculations, I realized that it should be solved using a computer. But it would be nice if you could provide a way to find this number, mathematically.

Answer 1

You have a computer, might as well use it.

However, for this particular problem, there are ways to optimize the search. Such as, for example, that $2$ is the only even prime among the positive integers. So if $n \neq 4$ is even, you already know that neither $n - 2$ nor $n + 2$ is prime. You can easily cut your computer's search time in half, give or take a few microseconds, just by ignoring even $n$.

Also, $n$ must be composite, because $n = 5$ is the only instance among the positive integers such that both $n - 2$ and $n + 2$ are prime. This suggests another optimization: if $n + 2$ is prime but any of the other conditions fail, increment $n$ by $4$ rather than $2$, e.g., $n = 27$, we see that $n + 2 = 29$ is prime but $n - 2 = 25 = 5^2$. Instead of moving on to $n = 29$, move on to $n = 31$.

Notice also that if $n \equiv \pm 2 \pmod 5$, then either $n - 2$ or $n + 2$ must be a multiple of $5$. Therefore you can concentrate your search on numbers having $1$, $5$ or $9$ for a least significant digit (base $10$).

I'm sure there are further optimizations you can apply. I could be wrong, but I don't think there's any mathematical algorithm that automatically guides you to the correct answer. You just have to search through the integers for the numbers that satisfy all five conditions (four primality conditions and the condition $10^4 < n < 10^5$).

Answer 2

I wrote a script in Swift that finds $n$. It can be run here

import Foundation
var n: Double = 10003

func isPrime(_ n: Double) -> Bool { //Translated from https://stackoverflow.com/a/2385999/6557621
    if n < 2 {return false}
    if n == 2 || n == 3 {return true}
    if n.truncatingRemainder(dividingBy: 2) == 0 || n.truncatingRemainder(dividingBy: 3) == 0 {return false}
    let sqrtN: Double = Double(sqrt(n)) + 1
    for i: Double in stride(from: 6, to: sqrtN, by: 6) {
        if (n.truncatingRemainder(dividingBy: (i - 1)) == 0) ||    (n.truncatingRemainder(dividingBy: (i + 1)) == 0) {return false}
    }
    return true
}

while !(isPrime(n - 2) && isPrime(n + 2) && isPrime(pow(n, 2) - 2) &&             isPrime(pow(n, 2) + 2)) {
    n += 2
}

print(n)

It prints $13761.0$