Let $n$ be a positive integer.

Define $f(n)$ to be the smallest non-negative number $x$, such that $x^2+n$ is prime (assuming that $x^2+n$ always is prime for some $x$, which is probably not proven yet, but a consequence of the Bunyakovsky-conjecture). In particalar, if $n$ is prime, we have $f(n)=0$

For example $f(54168539)=1008$ because $x^2+54168539$ is composite for $0\le x\le 1007$ and prime for $x=1008$. Moreover, $54168539$ is the smallest positive integer $n$ satisfying $f(n)>1000$

  • Given a number $k$, can we efficiently (without brute force) determine the smallest positive integer $n$ with $f(n)>k$ ? For example, what is the smallest $n$ with $f(n)>10^4$ ?

  • Is $f(n)$ surjective , in other words, does for every $k\ge 0$ exist a number $n>0$ with $f(n)=k$ ?

The existence of an $n$ with $f(n)>k$ for every $k$ can be shown with the chinese remainder theorem : We choose $n$ , such that $n\equiv 0\mod 2$ , $n\equiv -1\mod 3$ , $n\equiv -4\mod 5$ , $\cdots$, $n\equiv -(k-1)^2\mod p_{k}$ where $p_k$ is the $k$-th prime.

Then, the numbers $x^2+n$ with $0\le x\le k-1$ all have a prime factor not exceeding $p_k$. If we choose $n>p_k$, those numbers must be composite.

  • 1
    $\begingroup$ You could check the larger numbers in oeis.org/A275148. What is $f(7090889504)?$ That may well not be as large as you want. $\endgroup$ – Ross Millikan Apr 24 '17 at 21:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.