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

Question

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.

Answer 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)))})

Answer 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.

Answer 3

This is also only a partial solution that may provide more insight.

We can split into two cases, $x$ even and odd.

If $x$ is odd, then note that $i^x \equiv -(n-i)^x \mod n$. Then, consider $1^x+ 2^x...+n^x$ If $n$ is odd, we can pair up $1$ and $n-1$, etc. Each pair’s sum is divisible by $n$, $n^n$ is divisible by $n$ and the total is greater than $n$ and divisible by it and so composite. If $n$ is even, we can pair up 1 and $n$, etc and get that the sum is divisible by $n+1$ and divisible by it and is greater than it when either n or x are greater than 2.

If $x$ is even, then it’s trickier. By considering Vieta’s formula, it’s possible to show that $p| 1^x +2^x ... + (p-1)^x$ whenever $p-1$ does not divide $x$. This means that if $p$ divides $N$ and $p-1$ doesn’t divide $x$ then you can break up the sum into groups of size $p$ each divisible by $p$. Similarly if $p$ divides $N+1$, you can do the same thing by adding the $N+1$ term which is divisible by $p$. Similarly, you can double the sum and get terms from $1$ to $2N$ module $2N+1$. Thus, if $p$ doesn’t divide the sum and is a divisor of either $x$, $x+1$, or $2x+1$, then $p-1$ divides $N$.

Additionally, if $p^2$ divides $x$,$x+1$, or $2x+1$, then since each of the aforementioned groupings is the same module $p$ and their are now a multiple of $p$ of them, $p$ would divide the sum. This, in order for $p$ to not divide the sum, $x$, $x+1$, and $2x+1$ must not be divisible by its square.

In particular, this means for a given $n$, all of the primes of $x$, $x+1$, $2x+1$ are of the finite set of those for which $p-1$ divides $N$ and they are squarefree, so there are only a finite number of cases to check. Also, note that $x$,$x+1$, and $2x+1$ are relatively prime, so their primes are disjoint.

One other interesting fact is that if $p-1$ divides $n$, then everything is 0 or 1 mod p, so p divides the sum iff p divides $x - \lfloor x/p \rfloor$

It’s possible to use these facts to work through the small cases and quickly narrow things down to fairly large numbers.

In particular, if x is 2, the primes 2,3,5 divide $x$,$x+1$,$2x+1$, so 1,2,4 divides $N$, so $N$ is a multiple of 4. In fact, all the prime examples are the Fermat primes.

$x$ can’t be 3 since $x+1=4$ is not squarefree.

$x$ can’t be 4 since it’s squarefree.

If $x$ is 5, then to eliminate 5,2*3,11, we need $\operatorname{lcm}(5-1,2-1,3-1,11-1)=20$ to divide N. The smallest such example $1^{20}+2^{20}+3^{20}+4^{20}+5^{20}$ is divisible by 137. The fact that there can be a factor significantly larger than both $x$ and $n$ suggests that this kind of brute force approach with small factors is unlikely to completely solve the problem.

If $x$ is 6, then $2x+1$ is 13, so 12 divides N. Therefore $4=5-1$ divides N and $6=5+\lfloor 6/5 \rfloor$, so 5 will divide the sum of powers.

We can continue in the vein and eliminate many small numbers. In particular, I find that if $x$ is 10, then N must be a multiple of 60. If x is 21, then $N$ is a multiple of 210. If $x$ is 29, N is a multiple of $812=4*7*29$. Etc.

I’m not sure how to proceed from here. Even the simplest exceptional case here $1^{20}+2^{20}+3^{20}+4^{20}+5^{20}$ seems difficult to figure out that it’s composite and a multiple of 137 without brute force.