¿Puede una suma de consecutivos $n$ ¿las potencias de los dos son alguna vez iguales a una potencia de dos?

Question

Dejemos que $n,u,m\in \mathbb{N}$

$n_{u,m}$ es un número definido como

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

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

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

Pregunta : ¿Es cierta la siguiente afirmación?

Demuestra que $2^t$ no se puede escribir en $n_{u,m}$

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

Generalización del problema anterior

Dejemos que $d$ sea cualquier número entero positivo impar entonces demuestre que

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

Probé para $n_{u,1}$ y $n_{u,2}$ nunca es igual a una potencia de dos.

Prueba para $n_{u,1}\ne 2^t$

Prueba

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

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

Así que $$ (u+1)(2n+u)= 2^{t+1}$$

Caso $1$ : $u$ es $odd$

Entonces $u+1= even$ y $2n+u = odd$ implica $ even×odd \ne 2^{t+1}$ porque $ 2^{t+1}$ sólo contenido $even$ múltiplos excepto $1$ y $2n+u>1$ .

Caso $2$ : $u$ es $even$

Entonces $u+1= odd$ y $2n+u = even$ implica $odd×even \ne 2^{t+1}$ de forma similar al caso1

Así que ambos casos muestran una prueba completa para $n_{u,1} \ne 2^t$

Nota

Utilizando el método de interpolación de Newton, podemos calcular la fórmula de $n_{u,m}$ . Escribo la fórmula general al final del post.

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

Prueba para $n_{u,2}\ne 2^t$

Prueba

Supongamos $n_{u,2} = 2^t$

Podemos escribir $eq(1)$ como

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

Caso $1$ : $u =even$

$\implies u+1 = odd$

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

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

Pero sabemos que si $n$ es $even$ entonces $3n^2+3(2n+1)+2\ne even$

y si $n$ es $odd$ entonces $3n^2+3(2n+1)+2\ne even$

Por lo tanto, implica $3n^2+3(2n+1)+2\ne2^{t}$

Caso $2$ : $u =odd$

$\implies u+1=even=2^x$ para algunos $x$ .

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

Dónde $2^x2^y=2^{t+1}$

$\implies 2n+1= even$ Lo cual no es cierto.

Por lo tanto, ambos casos muestran una prueba completa para $n_{u,2}\ne 2^t$

Fórmula general para $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 $$

Dónde $n\in \mathbb{R}$ y $u,m\in \mathbb{Z^*}$ y $0^0=1$

Además, si ponemos $n=0$ entonces

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

---

Editar: $$\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 $$

Prueba

Sí, es un poco complicado pero creo que es cierto.

Puede que no haya intentado mucho que puedas rechazar usando el contraejemplo

Answer 1

Este es un argumento en el $m = 3$ -caso. Lo interesante es que muestra que $n_{u, 3}$ es divisible por $n_{u, 1}$ en cuyo momento el $m = 3$ -el caso se desprende de su tratamiento de la $m = 1$ -caso. Sería estupendo que para todos los $m \geq 3$ podríamos encontrar un $m' < m$ tal que $n_{u, m'}$ divide $n_{u, m}$ pero en la actualidad no sé si es el caso.

Así que el $m=3$ argumento. Esto se inspira en un post ahora borrado de alguien que trató el $0_{u, 3}$ caso.

Dejemos que $T_k$ denotan el $k$ El número triangular. Es bien sabido que la suma del primer $k$ tercera potencia es igual a $T_k^2$ . De ello se desprende que $n_{u, 3} = T_{n+u}^2 - T_{n-1}^2 = (T_{n+u} - T_{n-1})(T_{n+u} + T_{n-1})$ .

Mira el primer término de esta factorización, $T_{n+u} - T_{n-1}$ . Por un lado es un divisor de la cosa completa, así que de $n_{u, 3}$ . Por lo tanto, si esta última es una potencia de dos también lo es la primera. Por otro lado, $T_{n+u} - T_{n-1}$ es igual a $n_{u, 1}$ .

Conclusión: si $n_{u, 3}$ es una potencia de 2, también lo es $n_{u, 1}$ que ya demostró ser imposible.

Answer 2

No tengo una respuesta completa, pero espero que pueda ser de ayuda para otras personas que estén trabajando en este problema. ¡Realmente gracias y felicitaciones porque la pregunta parece muy rica y profunda! Al final hay un corolario y algunas consideraciones que se pueden saltar al principio :)

Suponemos que $u \ge 2, m \ge 1$ de lo contrario es falso. Cambiando ligeramente la notación para que $u$ es el número de sumandos, suponemos por ahora que $S_{u,m}(n):=\sum_{i=1}^u (n+i)^m = 2^t$ .

Lema cero . Supongamos que $u=ab$ con $a,b > 1$ . Entonces $S_{u,m}(n) \equiv a S_{b,m}(0) \pmod{b}$ .

En efecto, $$ 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} $$

Además, junto a $n$ los términos son exactamente todos los residuos posibles módulo $b$ , por lo que podemos suponer $n=0$ y obtenemos $S_{b,m}(0)$ .

Primer lema : $u$ es impar.

Prueba. El primer caso es $m$ incluso. Supongamos que $u= 2^kd$ con $d$ impar. Afirmamos que para $k \ge 1, S_{2^kd,m}(n) \equiv 2^{k-1} \pmod{2^k}$ . Por el lema 0, tenemos $S_{2^kd,m}(n) \equiv d S_{2^k,m}(0)$ para que $S_{2^kd,m}(n) \equiv 2^{k-1} \pmod{2^k}$ si $S_{2^k,m}(0) \equiv 2^{k-1} \pmod{2^k}$ .

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

Ahora demostramos por inducción en $k \ge 2$ que la tesis se mantiene. Módulo $2^{k+1}$ que tenemos: $$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) $$

En efecto, recordemos que por hipótesis inductiva $S_{2^k,m-1}(n) \equiv 2^{k-1} \pmod{2^k}$ y $m$ está en paz.

Si $m$ es impar, tenga en cuenta que

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

De modo que $2n+u+1$ es una potencia de dos (mayor que 2 debido a $n\ge 0, u\ge 2$ ). Así, $u$ es impar. Esta parte de la prueba se debe a Luca Vantaggio, un amigo mío :)

Segundo lema : $u$ es libre de cuadrados.

Supongamos que $u=p^2v$ con $p$ impar. Por el lema 0, tenemos que $S_{p^2v,m}(n) \equiv vp S_{p,m}(0) \equiv 0 \pmod{p}$ .

Definir para $n \in \mathbb{N}$ la función Eulero modificada $\hat{\varphi}(n) := \mathrm{lcm}(\{\varphi(p^k)\}_{p^k \mid \mid n} )$ .

Tercer lema : $\hat{\varphi}(u) \mid m$ . Además, para cada $p \mid u$ tenemos $ 2^t \equiv -(u/p) \pmod{p}$ .

Esto equivale a demostrar que si $p \mid u$ donde $p$ es impar, entonces $p-1 \mid m$ . Sea $g$ sea un generador módulo $p$ . Afirmamos que si $p-1 $ no divide $m$ entonces

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

y es $\equiv -1$ si $p-1 \mid m$ . En efecto, la multiplicación por $g$ permuta $\{1, \ldots, p-1\}$ para que $$ S_{p,m}(0) = (g\cdot 1)^m + \ldots+ (g \cdot (p-1))^m = g^m S_{p,m}(0)$$ Desde $g^m \neq 1$ obtenemos $S_{p,m} \neq 0 \pmod{p}$ .

Por otro lado, si $p-1 \mid m$ por el Pequeño Teorema de Fermat $$S_{p,m}(0) \equiv 1^m+ \ldots (p-1)^m \equiv 1+ \ldots 1 \equiv p-1 \equiv -1 \pmod{p} $$

Concluimos el lema observando que si $m$ no es divisible por $p-1$ , entonces por el lema cero (estableciendo $u=pv$ ): $$ S_{pv,m}(n) \equiv v S_{p,m}(0) \equiv 0 \pmod{p}$$

Y hemos terminado. Ser $p-1 \mid m$ también obtenemos $$ 2^t = S_{u,m}(n) \equiv v S_{p,m}(0) \equiv -v = -(u/p) \pmod{p} $$

Cuarto lema . $u \equiv \pm 1 \pmod{8} $ . A continuación mostramos que $m$ es par, y sabemos que $u$ es impar. Así pues, módulo 4 los sumandos son 0,1 alternativamente, de modo que la suma sólo puede ser $(u \pm 1)/2$ . Esto concluye.

Para mostrar cómo la combinación de estos lemas puede ser eficaz, damos un corolario que comprueba los casos pequeños.

Corolario . $m$ es par y $m \ge 16$ .

$m$ es incluso por $2 \mid \hat{\varphi}(u) \mid m$ . Ahora excluimos los números pares $\le 14$ .

• $m \neq 2,14$ . Si $p-1 \mid 14$ entonces $p-1 \mid 2$ porque 7 y 14 no dan primos. Así que para ambos $2,14$ tenemos $\hat{\varphi}(u) \mid 2$ lo que implica $u=3$ , imposible porque es $\equiv 3 \pmod{8}$ .

• $m\neq 4,8$ . Si $\hat{\varphi}(u) \mid 4$ entonces $u \mid 15$ . Los casos $u=3,5$ ya están cubiertos, así que nos queda $u=15$ . En este caso obtenemos $2^t \equiv -5 = 1 \pmod{3}$ es decir $t$ incluso. Pero entonces $2^t = 1,4 \pmod{5}$ que son diferentes de $-3$ .

• $m \neq 6$ . En este caso $\hat{\varphi}(u) \mid 6$ implica $u \mid 21$ . El caso $u=7$ puede excluirse debido a $2^t \equiv -1 \pmod{7}$ , lo cual es imposible. El caso $u=21 \equiv 5 \pmod{8}$ es imposible.

• $m=10$ . $\hat{\varphi}(u) \mid 10$ implica $u \mid 11\cdot 3$ . Los primos simples son imposibles debido a la congruencia módulo 8. El caso $u = 33$ es imposible porque $2^t \equiv -11 \equiv 1 \pmod{3}$ implica $t$ incluso, pero $2^{2s} \equiv 1,4,5,9,3 \neq -3 \pmod{11}$ .

• $m\neq 12$ . $\hat{\varphi}(u) \mid 12$ implica $u \mid 13 \cdot 7 \cdot 5 \cdot 3$ . Los primos simples son imposibles, como hemos visto anteriormente. Módulo 8, los únicos pares que podemos elegir son $3 \cdot 5$ (excluido antes), $13 \cdot 5$ (lo que produce una contradicción por la vía habitual $2^t \equiv -(u/p) \pmod{p}$ ), $13 \cdot 3$ (mismo argumento). Los únicos triples posibles módulo 8 son $7\cdot 5 \cdot 3, 13 \cdot 7\cdot 3, 13 \cdot 7 \cdot 5$ : todos ellos son imposibles de comprobar $2^t \pmod{7}$ (que sólo puede ser $1,2,4$ ). El número entero es imposible módulo 8.

Hemos llevado este método al máximo, ¡no podemos ir más allá, supongo! :)

Corolario 2 . Sin una gran calculadora, no podremos calcular con precisión los contraejemplos.

De hecho, hemos demostrado que $m \ge 16$ . Módulo $8$ lo menos posible $u$ es 17. Así que la suma es al menos $$ 0^{16} + \ldots + 16^{16} \ge \int_0^{16} x^{16} = \frac{16^{17}}{17} = 2^{68} / 17 \ge 2^{63} $$ que son como el bit de un long long int.

Nota: . No siempre las limitaciones $2^t \equiv -(u/p) \pmod{p}$ produce una contradicción. Por ejemplo, $u=35$ implica mediante algunos cálculos sencillos $t \equiv 7 \pmod{12}$ .

Pregunta . El caso que mis técnicas realmente no abordan es el caso en el que $u$ es primo. Sólo hay que excluir los casos en los que el orden de $2$ modulo $u$ es impar (por $2^t \equiv -1 \pmod{p}$ ), como en el caso de $u=7$ . Pero esto es realmente débil y sólo excluirá unos pocos casos.

A partir de ahora: ¿puede alguien excluir que $$ (n+1)^{p-1} + \ldots (n+p)^{p-1} $$ es una potencia de dos para algún primo $p$ ? Creo que esto sería un gran paso adelante, y probablemente implicará la divisibilidad para los primos mayores que $u$ (que nunca he considerado).

Answer 3

Aquí hay un código de prueba. Puedes copiarlo y pegarlo (anulando todo) en

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

Y prueba unos cuantos casos haciendo clic en el "run" verde de arriba y escribiendo en la pantalla negra de abajo. El código da la respuesta real si la suma tiene menos de ~ $18$ dígitos, de lo contrario sólo comprueba si la suma tiene un factor $2^{60}$ (que es una primera aproximación).

#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;
}

Para ser sinceros, hay un pequeño intervalo, es decir $ \log_2(u) + m* \log_2(u/2+n) \le 60 \le \log_2(u) + m* \log_2(u+n) $ en la que el ordenador dice que no es una potencia de dos, pero podría ser una potencia de dos menor que $2^{60}$ . Pero no te preocupes. No sucederá :)