Sea [math] C_n [/ math] el [math] n [/ math] -th entero encantador si se escribieron en orden ascendente: [math] 1, 2, 3, 5, 9, … [/ math], entonces [matemática] C_1 = 1 [/ matemática], [matemática] C_2 = 2 [/ matemática], [matemática] C_3 = 3 [/ matemática], [matemática] C_4 = 5 [/ matemática], y así sucesivamente. Debido a que los enteros tienen factorizaciones primas únicas, no hay dos números de la forma [matemáticas] 3 ^ i 5 ^ j [/ matemáticas] a menos que las [matemáticas] i [/ matemáticas] sy [matemáticas] j [/ matemáticas] correspondientes s son iguales (y no [math] 3 ^ i 5 ^ j [/ math] es igual a 2 por la misma razón), por lo que la secuencia de [math] C_n [/ math] s está aumentando estrictamente.
Lema 1. Para cualquier número encantador [math] C_n [/ math], existe un número encantador mayor que [math] C_n [/ math] pero no mayor que [math] 2C_n [/ math].
Prueba. [Matemática] C_n = 2 [/ matemática] o bien, para algunos enteros no negativos [matemática] i [/ matemática], [matemática] j [/ matemática], [matemática] C_n = 3 ^ i 5 ^ j [/ matemática ] En el caso [math] C_n = 2 [/ math], [math] 3 [/ math] es encantador y [math] 3 \ leq 4 = 2 (2) [/ math]. En el caso [matemática] C_n = 3 ^ i 5 ^ j [/ matemática], hay tres subcajas:
a) [matemática] i> 0 [/ matemática], en cuyo caso, [matemática] 3 ^ {i-1} 5 ^ {j + 1} [/ matemática] es encantadora, y [matemática] 3 ^ {i- 1} 5 ^ {j + 1} = \ frac {5} {3} \ left (3 ^ i \ right) \ left (5 ^ j \ right) \ leq 2 \ left (3 ^ i \ right) \ left (5 ^ j \ right) = 2C_n [/ math]
- ¿Existe un algoritmo mejor que o (n) para el siguiente problema: dado que un hashset contiene enteros y un número, encuentra el número más cercano al número dado?
- Si [matemática] p> 3 [/ matemática] es primo, ¿cómo se puede demostrar que si [matemática] p ^ k + p ^ l + p ^ m = n ^ 2 [/ matemática] tiene soluciones naturales [matemática] k , l, m, n [/ math], [math] p + 1 [/ math] es divisible por [math] 8 [/ math]?
- ¿Es solucionable la conjetura de Collatz?
- Usando divide y vencerás para s = (a ^ n), a> 0 y (n = 2 ^ k) a) muestra que el número de multiplicación usando recurrencia M (n) = M (n / 2) +1 para n> 1 y M (1) = 0 es?
- Si a y b son números enteros coprimos positivos, ¿puede mostrar que el único MCD posible de [matemáticas] a + b [/ matemáticas] y [matemáticas] a ^ 2 + b ^ 2 [/ matemáticas] son 1 y 2?
b) [matemáticas] i = 0 [/ matemáticas] y [matemáticas] j> 0 [/ matemáticas], en cuyo caso, [matemáticas] 3 ^ 2 5 ^ {j-1} [/ matemáticas] es encantador, y [ matemáticas] 3 ^ 2 5 ^ {j-1} = \ frac {9} {5} \ left (3 ^ 0 \ right) \ left (5 ^ j \ right) \ leq 2 \ left (3 ^ i \ right ) \ left (5 ^ j \ right) = 2C_n [/ math]
c) [matemáticas] i = 0 [/ matemáticas] y [matemáticas] j = 0 [/ matemáticas], en cuyo caso, [matemáticas] C_n = 1 [/ matemáticas], y [matemáticas] 2 [/ matemáticas] es encantador , y [matemáticas] 2 \ leq 2 (1) [/ matemáticas]. QED
Lema 2. Para cualquier número encantador [matemática] C_n [/ matemática], [matemática] C_n <C_ {n + 1} \ leq 2 C_n [/ matemática].
Prueba. Según el lema 1, hay un número encantador mayor que [matemática] C_n [/ matemática] pero no mayor que [matemática] 2 * C_n [/ matemática]. Llame a este encantador número [matemáticas] C_m [/ matemáticas]. Ahora, [matemática] m> n [/ matemática] porque los números encantadores se enumeraron en orden ascendente, y dado que [matemática] m [/ matemática] es un número entero, [matemática] m \ geq n + 1 [/ matemática]. Por lo tanto, [math] C_n <C_ {n + 1} \ leq C_m \ leq 2 C_n [/ math], entonces [math] C_n <C_ {n + 1} \ leq 2 C_n [/ math]. QED
Ahora, cada entero positivo menor que [math] C_2 [/ math] puede escribirse como una suma de diferentes enteros encantadores. Esto se debe a que [matemática] C_2 = 2 [/ matemática] y el único entero positivo menor que [matemática] 2 [/ matemática] es [matemática] 1 [/ matemática], que en sí mismo es encantador.
Suponga que ya se sabe que cada entero positivo menor que [math] C_n [/ math] puede escribirse como una suma de enteros encantadores distintos. Entonces, si [matemática] x [/ matemática] es un número entero con [matemática] C_n <x <C_ {n + 1} [/ matemática], por el Lema 2, se deduce que [matemática] C_n <x <2 C_n [ / math], entonces [math] C_n – C_n <x – C_n <2 C_n – C_n [/ math], y así, [math] 0 <x – C_n <C_n [/ math]. Por el supuesto, [math] x – C_n [/ math] puede escribirse como una suma de enteros encantadores distintos, y ninguno de ellos es [math] C_n [/ math], porque cada entero encantador es positivo y [math] x – C_n [/ math] es más pequeño que [math] C_n [/ math]. Por lo tanto, [math] x = \ left (x – C_n \ right) + C_n [/ math] puede escribirse como una suma de enteros encantadores distintos, porque [math] C_n [/ math] es encantador y no es igual a ninguno de los enteros encantadores cuya suma es igual a [matemáticas] x – C_n [/ matemáticas]. Por lo tanto, cada entero entre [matemática] C_n [/ matemática] y [matemática] C_ {n + 1} [/ matemática] (excluyendo ambos extremos) puede escribirse como una suma de enteros encantadores distintos. [math] C_n [/ math] en sí es encantador (por lo que es una suma de enteros encantadores distintos), y cada suposición positiva menor que [math] C_n [/ math] puede escribirse como una suma de enteros encantadores distintos por el supuesto . Por lo tanto, cada entero positivo menor que [math] C_ {n + 1} [/ math] puede escribirse como una suma de enteros encantadores distintos, porque es menor que [math] C_n [/ math], igual a [math ] C_n [/ math], o mayor que [math] C_n [/ math] (y menor que [math] C_ {n + 1} [/ math]).
Por lo tanto, por inducción, cada entero positivo menor que al menos uno de los [math] C_n [/ math] puede escribirse como una suma de enteros encantadores distintos. Dado que [math] C_n [/ math] crece sin límite (dado que, por ejemplo, su subsecuencia de los poderes de [math] 5 [/ math] lo hace), cada entero positivo es menor que al menos uno de los [math ] C_n [/ math], y por lo tanto, puede escribirse como una suma de enteros encantadores distintos. QED