10
$\begingroup$

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.

$\endgroup$
12
  • 5
    $\begingroup$ There are other cases, for example, $\;1^4+2^4=17\;,\;1^8+2^8=257\;.$ $\endgroup$
    – Angelo
    Commented May 1, 2021 at 1:08
  • $\begingroup$ Do you intend that $x$ is a (positive) integer? $\endgroup$ Commented May 1, 2021 at 1:08
  • 2
    $\begingroup$ 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$. $\endgroup$
    – fwd
    Commented May 1, 2021 at 1:14
  • 1
    $\begingroup$ 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$. $\endgroup$
    – K.defaoite
    Commented May 1, 2021 at 1:18
  • 1
    $\begingroup$ en.wikipedia.org/wiki/Faulhaber%27s_formula $\endgroup$
    – yoyo
    Commented May 1, 2021 at 1:29

3 Answers 3

22
$\begingroup$

There is a counter-example

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

enter image description here

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)))})
$\endgroup$
8
  • $\begingroup$ Well, just one counterexample is worth more than ten-thousand promising proof attempts. Very nice. $\endgroup$
    – Mike
    Commented May 1, 2021 at 6:26
  • $\begingroup$ WOW! I must admit I was quite convinced this conjecture was true. This is high up on my list of favorite counterexamples ever! $\endgroup$
    – K.defaoite
    Commented May 1, 2021 at 18:09
  • $\begingroup$ You could have saved yourself a lot of computation and just checked whether or not the number was prime on WolframAlpha ;) $\endgroup$
    – K.defaoite
    Commented May 1, 2021 at 18:11
  • 2
    $\begingroup$ @K.defaoite Wolfram alpha is obviously doing a pseudoprime test. The integer is very large. $\endgroup$
    – reuns
    Commented May 1, 2021 at 18:22
  • 2
    $\begingroup$ @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. $\endgroup$ Commented May 2, 2021 at 4:54
9
$\begingroup$

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.

$\endgroup$
16
  • 1
    $\begingroup$ I like this formula a lot. Where did you find it? $\endgroup$
    – K.defaoite
    Commented May 1, 2021 at 2:47
  • $\begingroup$ As I am learning the heuristic, just to make sure: Does it mean that there is no direct proof? $\endgroup$ Commented May 1, 2021 at 3:14
  • 1
    $\begingroup$ 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}$. $\endgroup$ Commented May 1, 2021 at 5:15
  • $\begingroup$ @JacobManaker Thanks, I've fixed it up. $\endgroup$ Commented May 1, 2021 at 6:17
  • 1
    $\begingroup$ @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. $\endgroup$ Commented May 1, 2021 at 6:20
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .