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

• There are other cases, for example, $\;1^4+2^4=17\;,\;1^8+2^8=257\;.$ Commented May 1, 2021 at 1:08
• Do you intend that $x$ is a (positive) integer? Commented May 1, 2021 at 1:08
• There are formulas for the sum of the first $n$ powers of natural numbers (at least for the first few $n$). By analyzing these formulas, one may perhaps argue using divisibility arguments that the sums are indeed composite for large $N$.
– fwd
Commented May 1, 2021 at 1:14
• This is interesting. Letting $$S(n,r)=\sum_{k=1}^n k^r$$ I have found no prime values other than the cases mentioned all the way up to $r=50,n=1000$. Commented May 1, 2021 at 1:18
• en.wikipedia.org/wiki/Faulhaber%27s_formula
– yoyo
Commented May 1, 2021 at 1:29

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

• Well, just one counterexample is worth more than ten-thousand promising proof attempts. Very nice.
– Mike
Commented May 1, 2021 at 6:26
• WOW! I must admit I was quite convinced this conjecture was true. This is high up on my list of favorite counterexamples ever! Commented May 1, 2021 at 18:09
• You could have saved yourself a lot of computation and just checked whether or not the number was prime on WolframAlpha ;) Commented May 1, 2021 at 18:11
• @K.defaoite Wolfram alpha is obviously doing a pseudoprime test. The integer is very large. Commented May 1, 2021 at 18:22
• @K.defaoite Wolfram's documentation on this point is poor. Wolfram Alpha is using Mathematica's PrimeQ function, which is a probable primality test despite not saying so anywhere in its manual page. You need to use ProvablePrimeQ to make certain. I let it grind away for a couple hours in this case since I was curious about how well Pari does against it, and the Mathematica version didn't finish--so, point to Pari. To be fair to Wolfram, it would be a safe bet that the output of PrimeQ and ProvablePrimeQ will never differ on input any human will ever use over the history of our species. Commented May 2, 2021 at 4:54

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.

• I like this formula a lot. Where did you find it? Commented May 1, 2021 at 2:47
• As I am learning the heuristic, just to make sure: Does it mean that there is no direct proof? Commented May 1, 2021 at 3:14
• Your analysis of each case (divisibility by $2$, divisibility by $3$) is wrong. The binomial is $\binom{N+1}{k+1}$, but you use $\binom{N+1}{k}$. Commented May 1, 2021 at 5:15
• @JacobManaker Thanks, I've fixed it up. Commented May 1, 2021 at 6:17
• @IsaacBrenig reuns has found a counterexample to your claim, so there is indeed no proof. This heuristic begins to explain why counterexamples are rare, at least. There's going to be a rat's nest of modular congruence conditions that will all have to work out just right for the result to happen to be prime. Commented May 1, 2021 at 6:20

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.