<s>[INST] how to prove that $1^x+2^x+3^x+4^x+\cdots+N^x$ will never sum to a prime number except $1^x+2^x$? I am a a web developer programming in PhP which is limited to large calculations, but running a quick script shows that $1^x+2^x+3^x+4^x+\cdots+N^x$ can never sum to a prime number unless in the case of $1^x+2^x$, such as in the cases of $x=1$ and $x=2$ where $1^1+2^1=3$ and $1^2+2^2=5$.
As a self learner, I am currently refreshing my learning in Algebra 2 (before moving on), and sometimes my mind wonders into questions that I just can't find the answers to (mostly because I am not familiar with the concerned topics). I tried finding an answer but if this is a duplicate with a relevant answer, please close and refer me to it.
How to prove (if possible) that $1^x+2^x+3^x+4^x+\cdots+N^x$ will never be the sum of a prime number, unless in the case of $1^x+2^x$, such as in the cases of $x=1$ and $x=2$ where $1^1+2^1=3$ and $1^2+2^2=5$?
Edit: $x$ and $N$ are positive integers
I appreciate any answers even if it is just a hint or a reference.
 [/INST] Faulhaber's formula is frankly not good. It does not deserve to be as popular as it is. A better formula is
$$1^x + 2^x + \cdots + N^x = \sum_{k=1}^x k! \left\{ {x \atop k}\right\} \binom{N+1}{k+1} \qquad (\text{for }x \geq 1).$$
Here $\left\{ {x \atop k}\right\}$ is a Stirling number of the second kind, which is a non-negative integer with simple combinatorial meaning much like the binomial coefficients $\binom{N+1}{k+1}$. This formula is cancellation-free and doesn't involve anything "mysterious" like the Bernoulli numbers.
From this formula, we've got $k!$ in each term, so it's pretty plausible that we'll "usually" get composites. Ok, but when do we actually get a composite?
First off, every term with $k \geq 2$ is divisible by $2$. The $k=1$ term is just $\binom{N+1}{2} = (N+1)N/2$. This will be even when $N=4m$ or $N=4m+3$. So, we can suppose $N=4m+1$ or $N=4m+2$.
Every term with $k \geq 3$ is divisible by $3$. When are the other two terms also divisible by $3$? When
$$\left\{{x \atop 1}\right\} \binom{N+1}{2} + \left\{{x \atop 2}\right\} \binom{N+1}{3} = \frac{(N+1)N}{2} + (2^{x-1} - 1) \frac{(N+1)N(N-1)}{6}$$
is divisible by $3$. This occurs for instance when $3 \mid \frac{(N+1)N}{2}$ and $3 \mid 2^{x-1} - 1$, so when $N=3m$ or $N=3m+2$ and $x$ is odd.
Now reuns has found a counterexample with 5 terms. That fits with this heuristic. A lot of modular congruence conditions have to work out simultaneously to get counterexamples.
</s>