Can a sum of consecutive $n$th powers ever equal a power of two?

Solution 1:

Here is an argument in the $m = 3$-case. What is interesting about it is that it shows that $n_{u, 3}$ is divisible by $n_{u, 1}$ at which point the $m = 3$-case follows from your treatment of the $m = 1$-case. It would be great if for all $m \geq 3$ we could find an $m' < m$ such that $n_{u, m'}$ divides $n_{u, m}$ but at present I don't know if that is the case.

So the $m=3$ argument. This is inspired by a now deleted post by someone who treated the $0_{u, 3}$ case.

Let $T_k$ denote the $k$'th triangular number. It is well known that the sum of the first $k$ third powers equals $T_k^2$. It follows that $n_{u, 3} = T_{n+u}^2 - T_{n-1}^2 = (T_{n+u} - T_{n-1})(T_{n+u} + T_{n-1})$.

Look at the first term in this factorization, $T_{n+u} - T_{n-1}$. On the one hand it is a divisor of the full thing, so of $n_{u, 3}$. Thus, if the latter is a power of two so is the former. On the other hand, $T_{n+u} - T_{n-1}$ equals $n_{u, 1}$.

Conclusion: if $n_{u, 3}$ is a power of 2, so is $n_{u, 1}$ which you already showed impossible.

Solution 2:

I don't have a full answer, but I hope it can be of help for other people that is working on this problem. Really thanks and congratulations because the question seems very rich and deep! In the end there is a corollary and some considerations you can skip to at the beginning :)

We are supposing that $u \ge 2, m \ge 1$ otherwise it is false. Slightly changing the notation so that $u$ is the number of summands, we suppose by now on that $S_{u,m}(n):=\sum_{i=1}^u (n+i)^m = 2^t$.

Lemma zero. Suppose $u=ab$, with $a,b > 1$. Then $S_{u,m}(n) \equiv a S_{b,m}(0) \pmod{b}$.

Indeed $$ S_{ab,m}(n) = \sum_{j=0}^{a-1} \sum_{i=1}^{b} (n+i+bj)^m \equiv \sum_{j=0}^{a-1} \sum_{i=1}^{b} (n+i)^m \equiv a S_{b,m}(n)\pmod{b} $$

Moreover, beside $n$, the terms are exactly all the possible remainders modulo $b$, so we can suppose $n=0$ and we get $S_{b,m}(0)$.

First lemma: $u$ is odd.

Proof. The first case is $m$ even. Suppose $u= 2^kd$ with $d$ odd. We claim that for $k \ge 1, S_{2^kd,m}(n) \equiv 2^{k-1} \pmod{2^k}$. By lemma 0, we have $S_{2^kd,m}(n) \equiv d S_{2^k,m}(0)$, so that $S_{2^kd,m}(n) \equiv 2^{k-1} \pmod{2^k}$ iff $S_{2^k,m}(0) \equiv 2^{k-1} \pmod{2^k}$.

For $k=1$ we have $S_{2,m}(0) = 0^m+1^m \equiv 1 \pmod{2}$. For $k=2$ we have $S_{4,m}(0) \equiv 1^m+2^m+3^m \equiv 2 \pmod{4}$.

Now we show by induction on $k \ge 2$ that the thesis holds. Modulo $2^{k+1}$ we have: $$S_{2^{k+1},m}(1) = \sum_{i=1}^{2^{k+1}} i^m = \sum_{i=1}^{2^k} i^m + \sum_{j=1}^{2^k} (2^k+j)^m \equiv $$ $$ S_{2^k,m}(1) + \sum_{j=1}^{2^k} (n+j)^m+ m (n+j)^{m-1} 2^k \equiv 2 S_{2^k,m}(n) + 2^km S_{2^k,m-1}(n) \equiv 2S_{2^k,m}(n) $$

Indeed, recall that by inductive hypothesis $S_{2^k,m-1}(n) \equiv 2^{k-1} \pmod{2^k}$, and $m$ is even.

If $m$ is odd, note that

$$ 2n +u+1 \mid \sum_{i=1}^u (n+i)^m +(n+u+1-i)^m = 2 S_{u,m}(n) = 2^{t+1}$$

So that $2n+u+1$ is a power of two (greater than 2 because of $n\ge 0, u\ge 2$). Thus $u$ is odd. This part of the proof is due to Luca Vantaggio, a friend of mine :)

Second lemma: $u$ is squarefree.

Suppose $u=p^2v$ with $p$ odd. By lemma 0, we have that $S_{p^2v,m}(n) \equiv vp S_{p,m}(0) \equiv 0 \pmod{p}$.

Define for $n \in \mathbb{N}$ the modified Eulero function $\hat{\varphi}(n) := \mathrm{lcm}(\{\varphi(p^k)\}_{p^k \mid \mid n} )$.

Third lemma: $\hat{\varphi}(u) \mid m$. Moreover, for every $p \mid u$ we have $ 2^t \equiv -(u/p) \pmod{p}$.

This is equivalent to show that if $p \mid u$ where $p$ is odd, then $p-1 \mid m$. Let $g$ be a generator modulo $p$. We claim that if $p-1 $ does not divide $m$, then

$$S_{p,m}(0)= 1^m+ \ldots +(p-1)^m \equiv 0 \pmod{p}$$

and it is $\equiv -1$ if $p-1 \mid m$. Indeed, the multiplication by $g$ permutes $\{1, \ldots, p-1\}$, so that $$ S_{p,m}(0) = (g\cdot 1)^m + \ldots+ (g \cdot (p-1))^m = g^m S_{p,m}(0)$$ Since $g^m \neq 1$, we get $S_{p,m} \neq 0 \pmod{p}$.

On the other hand, if $p-1 \mid m$ by Fermat Little Theorem $$S_{p,m}(0) \equiv 1^m+ \ldots (p-1)^m \equiv 1+ \ldots 1 \equiv p-1 \equiv -1 \pmod{p} $$

We conclude the lemma by observing that if $m$ is not divisible by $p-1$, then by lemma zero (setting $u=pv$): $$ S_{pv,m}(n) \equiv v S_{p,m}(0) \equiv 0 \pmod{p}$$

And we are done. Being $p-1 \mid m$, we also get $$ 2^t = S_{u,m}(n) \equiv v S_{p,m}(0) \equiv -v = -(u/p) \pmod{p} $$

Fourth lemma. $u \equiv \pm 1 \pmod{8} $. We show below that $m$ is even, and we know that $u$ is odd. Thus modulo 4 the summands are 0,1 alternating, so that the sum can only be $(u \pm 1)/2$. This concludes.

As to show how combining these lemmas can be effective, we give a corollary checking small cases.

Corollary. $m$ is even and $m \ge 16$.

$m$ is even because of $2 \mid \hat{\varphi}(u) \mid m$. Now we exclude the even numbers $\le 14$.

• $m \neq 2,14$. If $p-1 \mid 14$, then $p-1 \mid 2$ because 7 and 14 does not yield primes. So for both $2,14$ we have $\hat{\varphi}(u) \mid 2$ which implies $u=3$, impossible because it is $\equiv 3 \pmod{8}$.

• $m\neq 4,8$. If $\hat{\varphi}(u) \mid 4$, then $u \mid 15$. The cases $u=3,5$ are already covered, so we are left with $u=15$. In this case we get $2^t \equiv -5 = 1 \pmod{3}$, i.e $t$ even. But then $2^t = 1,4 \pmod{5}$ which are different from $-3$.

• $m \neq 6$. In this case $\hat{\varphi}(u) \mid 6$ implies $u \mid 21$. The case $u=7$ can be excluded because of $2^t \equiv -1 \pmod{7}$, which is impossible. The case $u=21 \equiv 5 \pmod{8}$ is impossible.

• $m=10$. $\hat{\varphi}(u) \mid 10$ implies $u \mid 11\cdot 3$. The single primes are impossible because of the congruence modulo 8. The case $u = 33$ is impossible because $2^t \equiv -11 \equiv 1 \pmod{3}$ implies $t$ even, but $2^{2s} \equiv 1,4,5,9,3 \neq -3 \pmod{11}$.

• $m\neq 12$. $\hat{\varphi}(u) \mid 12$ implies $u \mid 13 \cdot 7 \cdot 5 \cdot 3$. Single primes are impossible as we have seen above. Modulo 8, the only pairs we can choose are $3 \cdot 5$ (excluded before), $13 \cdot 5$ (which yield a contradiction by the usual $2^t \equiv -(u/p) \pmod{p}$ ), $13 \cdot 3$ (same argument). The only possible triples modulo 8 are $7\cdot 5 \cdot 3, 13 \cdot 7\cdot 3, 13 \cdot 7 \cdot 5$: they are all impossible by checking $2^t \pmod{7}$ (which can only be $1,2,4$). The whole number is impossible modulo 8.

We have pushed this method to the maximum, we cant go further i guess! :)

Corollary 2. Without a big calculator, we will not be able to precisely calculate counterexamples!

Indeed, we have shown that $m \ge 16$. Modulo $8$, the least possible $u$ is 17. So the sum is at least $$ 0^{16} + \ldots + 16^{16} \ge \int_0^{16} x^{16} = \frac{16^{17}}{17} = 2^{68} / 17 \ge 2^{63} $$ which are about the bit of a long long int.

Remark. Not always the constraints $2^t \equiv -(u/p) \pmod{p}$ yield a contradiction. For example, $u=35$ implies by some simple calculations $t \equiv 7 \pmod{12}$.

Question. The case that my techniques really does not address is the case in which $u$ is prime. One can just exclude the cases in which the order of $2$ modulo $u$ is odd (because of $2^t \equiv -1 \pmod{p}$), like in the case of $u=7$ . But this is really weak and will exclude only a few cases.

Henceforth: can someone exclude that $$ (n+1)^{p-1} + \ldots (n+p)^{p-1} $$ is a power of two for some prime $p$? I think this would be a great step ahead, and it will probably involve the divisibility for primes greater than $u$ (that I have never considered).

Solution 3:

Here it is a code for testing. You can copy and paste it (overriding everything) into

https://www.onlinegdb.com/online_c++_compiler

And try a few cases by clicking the green "run" above and writing in the black screen below. The code gives the real answer if the sum has less than ~$18$ digits, otherwise it only checks if the sum has a factor $2^{60}$ (which is a first approximation).

#include <iostream>
#include <cmath>
using namespace std;

long long int modpow(long long int a,long long int b,long long int n) {
    if (b==0) return 1;
    if (n <= 1) return 0;
    if (b==1) return a%n;

    if (b%2 == 0) {
        return (modpow(a,b/2,n)*modpow(a,b/2,n))%n;
    } else {
        return (modpow(a,(b-1)/2,n)*modpow(a,(b-1)/2,n)*a)%n;
    }
}

int main()
{   
    long long int n,u,m;
    cout << "Please enter the value for n" << endl;
    cin >> n;
    cout << "Please enter the value for u" << endl;
    cin >> u;
    cout << "Please enter the value for m" << endl;
    cin >> m;
    long long int s=0; 
    long long int i;
    long long int L = pow(2,60);
    for(i=1; i<=u;i++) {
        s+=modpow(n+i,m,L);
    }

    if( s== 0) {
        cout << "There is a veery good probability that it is a power of 2! You guessed it!" << endl;
    } else if (m*(log(u/2+n))+log(u)  < 60*log(2) )  {
        while (s %2 == 0) {
            s= s/2;
        }
        if (s > 1) {
            cout << " It is not a power of 2." << endl;
        } else {
            cout << "It is a power of 2! YOU ARE GREAT!" << endl;
        }
    } else {
        cout << "It is not a power of 2." << endl;
    }
    return 0;
}

To be honest, there's a small interval, i.e. $ \log_2(u) + m* \log_2(u/2+n) \le 60 \le \log_2(u) + m* \log_2(u+n) $ in which the computer says it is not a power of two, but it could be a power of two smaller than $2^{60}$. But dont worry. It wont happen :)