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$?

Solution 1:

There is a counter-example

$$A=\sum_{n=1}^5 n^{1440}$$

It took about 30 minutes to run the primality test, a faster check is with

         ispseudoprime(sum(n=1,5,n^1440))

that you can try there https://pari.math.u-bordeaux.fr/gp.html

My script to find more candidates ($A$ is the smallest one)

      lambda(n)=znstar(n)[2][1];  # carmichael function
      f(a,b) =sum(j=1,a,j^b);
      maxlog=100000;
      for (n=3,300,{ b=lambda(n*(n+1)); l = b*log(n); for (k=1,floor( maxlog/l), if(ispseudoprime(f(n,k*b)), print("prime ",n," ",k*b),print(n," ",k*b)))})

Solution 2:

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.