27
$\begingroup$

Let $n,u,m\in \mathbb{N}$

$n_{u,m}$ is a number defined as

$$n_{u,m}= n^m+(n+1)^m+(n+2)^m+...+(n+u)^m$$

$$= \sum_{i=0}^{u}(n+i)^m$$

example: $3_{2,4}=3^4+(3+1)^4+(3+2)^4=962$

Question: Is the following claim true?

Show that $2^t$ cannot be written in $n_{u,m}$

$$n_{u,m} = \sum_{i=0}^{u}(n+i)^m \ne 2^t \ \ \ \ \ \forall n,u,m,t\in \mathbb{N}$$

Generalization of above problem

Let $d$ be any odd positive integer then show that

$$\sum_{q=0}^{u}(n+qd)^{m}\ne 2^t \ \ \ \ \forall n,u,m,t\in\mathbb{N}$$

I proved for $n_{u,1}$ and $n_{u,2}$ never equals a power of two.

Proof for $n_{u,1}\ne 2^t$

Proof

Let suppose $$n_{u,1} = n+(n+1)+...+(n+u)$$

$$=\frac{(u+1)(2n+u)}{2}= 2^t$$

So $$ (u+1)(2n+u)= 2^{t+1}$$

Case$1$: $u$ is $odd$

Then $u+1= even$ and $2n+u = odd$ it implies $ even×odd \ne 2^{t+1}$ because $ 2^{t+1}$ content only $even$ multiples except $1$ and $2n+u>1$.

Case$2$: $u$ is $even$

Then $u+1= odd$ and $2n+u = even$ it implies $odd×even \ne 2^{t+1}$ similarly as case1

So both cases shows complete proof for $n_{u,1} \ne 2^t$

Note

By using Newton's interpolation method, we can calculate formula for $n_{u,m}$. I write the general formula at bottom of the post.

So $$ n_{u,2}=n^2(u+1)+(2n+1)\frac{(u+1)u}{2} +\frac{(u+1)u(u-1)}{3} \ \ \ \ \ \ ...eq(1)$$

Proof for $n_{u,2}\ne 2^t$

Proof

Let suppose $n_{u,2} = 2^t$

We can write $eq(1)$ as

$$ (u+1)(6n^2+3(2n+1)u+2u(u-1))= 3×2^{t+1} \ \ \ \ ...eq(2)$$

Case$1$: $u =even$

$\implies u+1 = odd$

$\implies u+1=3$ $\ \ \ $ By $eq(2)$

$\implies 3n^2+3(2n+1)+2=2^{t}=even$

But we know, if $n$ is $even$ then $3n^2+3(2n+1)+2\ne even$

and if $n$ is $odd$ then $3n^2+3(2n+1)+2\ne even$

Hence it implies $3n^2+3(2n+1)+2\ne2^{t}$

Case$2$: $u =odd$

$\implies u+1=even=2^x$ for some $x$.

$\implies 6n^2+3(2n+1)u+2u(u-1)= even=3×2^y$ for some $y$.

Where $2^x2^y=2^{t+1}$

$\implies 2n+1= even$, which is not true.

Hence both cases shows complete proof for $n_{u,2}\ne 2^t$

General formula for $n_{u,m}$

$$n_{u,m}=\sum_{i=0}^{m} \binom{u+1}{i+1} \sum_{j=i}^{m}\binom{m}{j}n^{m-j}\sum_{k=0}^{i}(i-k)^j(-1)^k\binom{i}k $$

Where $n\in \mathbb{R}$ and $u,m\in \mathbb{Z^*}$ and $0^0=1$

Moreover if we put $n=0$ then

$$0_{u,m}=\sum_{l=0}^{u}l^{m}$$ $$=\sum_{i=0}^{m}\binom{u+1}{i+1}\sum_{k=0}^{i}(i-k)^i(-1)^k\binom{i}k $$


Edit: $$\sum_{q=0}^{u}(n+qd)^{m}=\sum_{i=0}^{m} \binom{u+1}{i+1}\sum_{j=i}^{m}\binom{m}{j}n^{m-j}d^j\sum_{k=0}^{i}(i-k)^j(-1)^k\binom{i}k $$

Proof

Yes, It is a bit complicated but I believe it is true.

I may not have tried much that you could reject using counter example

$\endgroup$
8
  • $\begingroup$ So $k_m$ secretly depends on $n$ and $u$ in addition to $m$? $\endgroup$ – hmakholm left over Monica Sep 25 '19 at 19:25
  • 1
    $\begingroup$ for more convenient I changed notation $k_m$ to $n_{u,m}$ $\endgroup$ – Pruthviraj Sep 25 '19 at 20:29
  • 2
    $\begingroup$ Plainly, there must be an even number of odd terms if the sum is going to be even. $\endgroup$ – Keith Backman Sep 25 '19 at 20:49
  • 3
    $\begingroup$ I would add $m,u > 0$ otherwise it is trivial $\endgroup$ – Andrea Marino Sep 29 '19 at 16:32
  • 1
    $\begingroup$ Now check M.O. Post mathoverflow.net/q/348186/149083 $\endgroup$ – Pruthviraj Dec 12 '19 at 6:11
7
+25
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ I think that Faulhaber's polynomials suggest that often $n_{u,1}$ divides $n_{u,m}$, but this is not always the case. Also, for example, $2^m+3^m+4^m$ does not divide $2^5+3^5+4^5$ for $0 \lt m \lt 5$. $\endgroup$ – BillyJoe Oct 3 '19 at 9:39
4
$\begingroup$

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

$\endgroup$
9
  • $\begingroup$ At the beginning of first claim in the iff statement is it also assumed $d \equiv 1$ mod $2^k$? And what does a triple subscript on $S$ mean? $\endgroup$ – Ben Sep 29 '19 at 23:04
  • 1
    $\begingroup$ Sorry, I had another notation before: $S_{k,d,m}$ would be $S_{2^kd,m}$. No, it is not assumed. Note that if $d=(2r+1)$ then $(2r+1)2^{k-1} \equiv 2^kr+ 2^{k-1} \equiv 2^{k-1} \pmod{2^k} $ $\endgroup$ – Andrea Marino Sep 29 '19 at 23:16
  • $\begingroup$ @AndreaMarino thank you, it's really helpful and motivated, I just need time to better understand to your solution and going deeper. $\endgroup$ – Pruthviraj Oct 2 '19 at 13:52
  • $\begingroup$ Thanks. If you have doubts do not hesitate to ask :) $\endgroup$ – Andrea Marino Oct 2 '19 at 14:00
  • $\begingroup$ @AndreaMarino I wonder if you could explain what is meant by "$S_{4,m}(0) \equiv 1^m+2^m+3^m \equiv 2 \pmod{4}$, distinguishing the cases $m$ odd or even". For odd $m\ge 3$ we have sum $0$ mod $4$. $\endgroup$ – S. Dolan Oct 2 '19 at 17:10
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.