Professor Halfbrain has spent the last few days (and sleepless nights) with analyzing integer numbers of the form $~N_x(n):=n^x+x~$. The professor computed and analyzed thousands and thousands of these numbers, and made a number of fascinating observations:

  • For $x=1$, the number $N_1(6)=6^1+1=~7$ is prime.
  • For $x=2$, the number $N_2(3)=3^2+2=11$ is prime.
  • For $x=3$, the number $N_3(4)=4^3+3=67$ is prime.
  • For $x=4$, the number $N_4(1)=1^4+4=~5$ is prime.
  • For $x=5$, the number $N_5(2)=2^5+5=37$ is prime.

And so on. And so on. Finally, the professor detected the following extremely deep theorem.

Professor Halfbrain's theorem:
For every positive integer $x$, there exists a positive integer $n$ so that $N_x(n)$ is prime.

This puzzle asks you to decide the correctness of this theorem. If it is correct, then provide a convincing argument for it. If it is incorrect, then state the smallest positive integer $x$ for which the statement is violated.


1 Answer 1


Professor Halfbrain's theorem is incorrect.

For $x=27$ and any $n$, there is a factorization $$N_{27}(n)=(n^9+3)(n^{18}-3n^9+9)$$ as a product of two integers bigger than $1$, so $N_{27}(n)$ can never be prime.

More generally, whenever $k\geq 3$ is odd, there is a factorization $$N_{k^k}(n)=\left(n^{k^{k-1}}+k\right)\left(\sum_{i=0}^{k-1} (-k)^{k-1-i}n^{i k^{k-1}}\right), $$ so $N_{k^k}(n)$ is never prime.

A computer search determined that $N_x$ does take a prime value for $x=6,7,\ldots,26$, so $x=27$ is the smallest counterexample. The first prime values are: \begin{align*} N_{6}(1)&=7\\N_{7}(16)&=268435463\\N_{8}(3)&=6569\\N_{9}(2)&=521\\N_{\ 10}(1)&=11\\N_{11}(32)&=36028797018963979\\N_{12}(1)&=13\\N_{13}(118)&\ =859935929762876868984659981\\N_{14}(417)&=\ 4807339234680508004200143948920808143\\N_{15}(2)&=32783\\N_{16}(1)&=\ 17\\N_{17}(14)&=30491346729331195921\\N_{18}(1)&=19\\N_{19}(22)&=\ 32064977213018365645815827\\N_{20}(81)&=\ 147808829414345923316083210206383297621\\N_{21}(76)&=\ 3141126580731587340586460636236874776597\\N_{22}(1)&=23\\N_{23}(12)&=\ 6624737266949237011120151\\N_{24}(55)&=\ 587089817274070447368135511875152587890649\\N_{25}(28)&=\ 1509909033949224437981629384719597593\\N_{26}(15)&=\ 3787675244106352329254150390651\\ \end{align*}

  • $\begingroup$ Wow, that was quick. Is $x=27$ the smallest positive integer for which the statement is violated? $\endgroup$
    – Gamow
    Commented Mar 5, 2016 at 14:52
  • $\begingroup$ I'm not sure. For $x=4$ there is a factorization $N_4(n)=(n^2+2n+2)(n^2-2n+2)$, which is only prime for $n=1$. Mathematica did not find a factorization of $N_x(n)$ (as a polynomial) for any other $x<27$. It is conjectured that an integer polynomial takes infinitely many prime values provided that (1) the polynomial is irreducible, and (2) there is no $p$ for which every value of the polynomial is divisible by $p$. The second condition can be checked for the $N_x$, so if Mathematica's factorizations are correct, there should be a prime value of $N_x$ for each $x<27$. I'll try computer a search $\endgroup$ Commented Mar 5, 2016 at 15:23
  • $\begingroup$ Yes, $N_x$ takes a prime value for every $x\leq 26$ (the first prime value for $x=14$ happens for $n=417$, so this would be hard to check by hand). $\endgroup$ Commented Mar 5, 2016 at 15:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.