¿Cuántos términos diferentes hay en [matemáticas] (x ^ {13} + x ^ 7 + 1) ^ {100}? [/ Matemáticas]

Answer 1

Cualquier potencia de [math] x [/ math] en el resultado debe tener la forma [math] (x ^ {13}) ^ j (x ^ 7) ^ k (1) ^ {100-jk} = x ^ {13j + 7k} [/ matemática] con [matemática] j, k \ geq 0 [/ matemática] y [matemática] j + k \ leq 100 [/ matemática].

Así, por ejemplo, [math] x ^ {1300} [/ math] aparece en el producto, al igual que [math] x ^ {27} [/ math] pero [math] x ^ {3} [/ math] y [matemáticas] x ^ {24} [/ matemáticas] no.

Obviamente, podemos representar cualquier número entero como una combinación lineal de estos dos números; podríamos tener que usar números negativos. ¿Qué números dentro del rango [0,1300] tienen soluciones en enteros no negativos?

Dada una ecuación lineal de diofantina [matemática] ax + por = c [/ matemática], la resolvemos usando el Algoritmo Euclidiano Extendido para encontrar [matemática] n, m [/ matemática] tal que [matemática] an + bm = \ gcd ( a, b) [/ matemáticas]. En este caso tenemos [math] 13 \ cdot -1 + 7 \ cdot 2 = 1 [/ math]. (a = 13, b = 7, n = -1, m = 2)

La solución general para un caso donde el MCD es 1 es:

[matemáticas] x = nc + bk [/ matemáticas], [matemáticas] y = mc – ak [/ matemáticas]

Queremos permitir [math] x = 0 [/ math] o [math] y = 0 [/ math] por lo que tenemos que transformar el problema un poco. [matemática] ax + by = c [/ matemática] con [matemática] x, y [/ matemática] no negativa si y solo si [matemática] a (x’-1) + b (y’-1) = c [/ matemática] con [matemática] x ‘, y’ [/ matemática] positiva, o [matemática] ax ‘+ por’ = c + a + b [/ matemática], por lo que queremos encontrar cuál [matemática] c [/ matemática ] en nuestro rango tenemos soluciones enteras positivas para [matemáticas] 13x ‘+ 7y’ = c + 20 [/ matemáticas].

Usando el formulario general anterior tenemos

[matemática] -1 (c + 20) + 7k> 0 [/ matemática] y [matemática] 2 (c + 20) – 13k> 0 [/ matemática]

LÍMITES 1 y 2: [matemática] k> \ frac {c + 20} {7} [/ matemática] y [matemática] k <\ frac {2 (c + 20)} {13} [/ matemática]

Por lo tanto, para que [math] x, y [/ math] sea positivo, debe haber algún número entero [math] k [/ math] con [math] (c + 20) / 7 <k <2 (c + 20) / 13 [/ matemáticas]

Verifique: c = 7 tiene una solución. [matemáticas] 27/7 <k <2 \ cdot 27/13 [/ matemáticas] tiene exactamente una solución entera, k = 4.

Comprobación: c = 8 no tiene solución. [matemáticas] 28/7 <k <2 \ cdot 28/13 [/ matemáticas] no tiene soluciones enteras, ya que la comparación es "nítida".

También tenemos límites superiores [matemática] x + y \ leq 100 [/ matemática], o [matemática] x ‘+ y’ \ leq 102 [/ matemática]. Traducido al aceptable [math] k [/ math] nos da el límite adicional

[matemática] -1 (c + 20) + 7k + 2 (c + 20) – 13k \ leq 102 [/ matemática]

LÍMITE 3: [matemáticas] k \ geq \ frac {c – 82} {6} [/ matemáticas]

Ahora, todo lo que realmente necesitamos para terminar es papel cuadriculado y un lápiz afilado. 🙂

El punto de cruce donde se encuentran los límites inferiores es [matemática] c = 694 [/ matemática].

Más importante aún, se garantiza que [math] k [/ math] tendrá un valor entero siempre que los límites estén separados por más de 1 entero

[matemática] \ frac {2 (c + 20)} {13} – \ frac {c + 20} {7}> 1 [/ matemática] cuando [matemática] c> 71 [/ matemática]

[matemática] \ frac {2 (c + 20)} {13} – \ frac {c-82} {6}> 1 [/ matemática] cuando [matemática] c <1228 [/ matemática]

Por lo tanto, todos los poderes de [matemática] x [/ matemática] entre [matemática] 72 [/ matemática] y [matemática] 1227 [/ matemática] están representados, dejándonos con un puñado de casos para verificar.

Podemos obtener un poco más de millas de nuestro sistema de desigualdades lineales usando el Teorema de Pick. Para eso necesitamos crear un triángulo cuyos vértices sean todos puntos enteros, y para el que ningún valor ‘c’ tenga más de una ‘k’. Veamos el fondo de nuestro politopo

[matemáticas] \ frac {c + 20} {7} <k <\ frac {2 (c + 20)} {13} [/ matemáticas]

[matemática] c = -20, k = 0 [/ matemática] es un punto entero (el punto inferior de nuestro simplex). [matemática] c = 71, k = 13 [/ matemática] y [matemática] c = 71, k = 14 [/ math] define los otros dos puntos de un triángulo que contiene todas las soluciones. Para usar el teorema de Pick

[matemáticas] A = B / 2 + I – 1 [/ matemáticas]

Necesitamos el área, [matemática] A = 91/2 [/ matemática], y el número de puntos en el borde que, recursivamente, nos piden que encontremos el número de soluciones para una ecuación lineal de diofantina nuevamente. 🙂 Pero esta vez podemos simplemente recitarlos. El límite izquierdo tiene soluciones [matemáticas] c = 7n + 1, k = n + 3 [/ matemáticas] y el límite derecho tiene soluciones enteras [matemáticas] c = 13n + 6, k = 2n + 4 [/ matemáticas], entonces los puntos de borde en nuestro triángulo son:

Los tres vértices (-20,0), (71, 13), (71, 14)

Lado izquierdo: (-13,1), (-6,2), (1,3), (8, 4), (15,5),… (64,12): 12 puntos límite

Lado derecho: (-7,2), (6,4), (19, 6),… (58, 12): 6 puntos límite

[matemáticas] 91/2 = 21/2 + I – 1 [/ matemáticas], por lo que hay soluciones enteras [matemáticas] I = 36 [/ matemáticas] en esa parte del símplex.

Haciendo lo mismo para la parte superior del politopo, tenemos el triángulo [matemáticas] (1306,204) [/ matemáticas], [matemáticas] (1228, 191) [/ matemáticas] y [matemáticas] (1228,192) [/matemáticas]. El límite izquierdo ahora tiene soluciones enteras [matemáticas] c = 6n + 4, k = n-13 [/ matemáticas], entonces

Lado izquierdo: (1300,203),… (1234, 192): 12 puntos límite

Lado derecho: (1293,202),… (1241, 194): 5 puntos límite:

[matemática] 78/2 = 20/2 + I – 1 [/ matemática], entonces es [matemática] I = 30 [/ matemática] soluciones enteras más.

Pero, hay un paso más. Debido a que BOUND 3 es [math] \ geq [/ math] en lugar de [math]> [/ math], todos los puntos límite en el lado izquierdo son soluciones válidas, incluyendo (1228,191) pero no (1306,204 ) Eso nos da 13 soluciones adicionales.

Ahora es el momento de agregarlos todos:

[matemática] 30 + 13 = 43 [/ matemática] valores de c mayores que [matemática] 1228 [/ matemática] tienen una solución

[matemática] 36 [/ matemática] valores de c menores que [matemática] 71 [/ matemática] tienen una solución

Todos los valores [matemática] 1156 [/ matemática] de c entre [matemática] 72 [/ matemática] y [matemática] 1227 [/ matemática] tienen una solución

Eso da 1235 términos.

Cheque:

trinomio = [0, 7, 13]
términos = conjunto ([0])
para n en xrange (100):
newTerms = set ()
para i en términos:
para t en trinomio:
newTerms.add (i + t)
términos = nuevos términos

imprimir len (términos)

Resultado: 1235

Answer 2

Es fácil verificar que:

[matemáticas] (x ^ 0 + x ^ 7 + x ^ {13}) ^ 2 = x ^ 0 + 2x ^ 7 + 2x ^ {13} + x ^ {14} + 2x ^ {20} + x ^ { 26} [/ matemáticas]

¿Pero sabías que podrías obtener esta respuesta con una convolución?

Aquí está el código de Matlab:

conv ([1 0 0 0 0 0 0 1 0 0 0 0 0 1], [1 0 0 0 0 0 0 1 0 0 0 0 0 1])

ans = 100000020000021000002000001

Si hace esto 99 veces, obtendrá los coeficientes de [matemática] (x ^ 0 + x ^ 7 + x ^ {13}) ^ {100} [/ matemática]:

Los coeficientes polinómicos obtenidos mediante convolución. Sin embargo, el patrón general es gaussiano, con un patrón periódico adicional con un período de ~ 6.5.

Teorema de convolución

Usando el teorema de convolución, podemos hacer esto en un solo paso, elevando el espectro de frecuencia de la secuencia inicial de coeficientes polinomiales a la potencia [matemática] 100 ^ {th} [/ matemática] (ver código en la parte inferior) . Sin embargo, se debe tener cuidado con respecto a la precisión numérica: la diferencia de escala de los coeficientes más altos con respecto a los coeficientes unitarios debe estar dentro de los límites del software utilizado. Matlab tuvo algunos problemas con este poder [matemático] 100 ^ {th} [/ matemático], que se puede ver en el diagrama logarítmico a continuación:

Los valores en la parte derecha de la gráfica son claramente artefactos, ya que definitivamente no hay términos polinomiales con un orden superior a 1400.

Para evitar esta diferencia de escala extrema, el procedimiento se puede dividir en pasos separados. Con este fin factoricé el exponente de la siguiente manera: [matemática] 100 = 2 * 2 * 5 * 5 [/ matemática].

Entonces, en la primera iteración, el espectro solo es cuadrado. Ahora, después de la transformada inversa de Fourier, los coeficientes resultantes se reemplazan por valores binarios, en los que cada coeficiente distinto de cero se normaliza a un ‘1’. Esto está permitido porque: a) solo estamos interesados ​​en el número de términos (no en los valores de los coeficientes), yb) todos los coeficientes iniciales son positivos (de lo contrario, algunos coeficientes podrían cancelarse).

Resultado:

• Como se esperaba, la primera iteración resultó en 6 términos distintos de cero
• Al cuadrar nuevamente el espectro, se obtuvieron 15 términos distintos de cero
• Tomando la quinta potencia, dio 195 términos distintos de cero
• Y tomando la quinta potencia de nuevo, dio 1235 términos finales distintos de cero

Código de Matlab:

polCoefs = ceros (1, 1400);
polCoefs ([1,8,14]) = 1;
primFactors = [2 2 5 5]; % la descomposición primaria de 100
para k = 1: 4
p = primFactors (k);
polCoefs = real (ifft (fft (polCoefs). ^ p));
% normalizar a 1 para evitar inestabilidad numérica
polCoefs = round (max (0, (min (1, polCoefs)))));
sum (polCoefs)
fin
sum (polCoefs)

Answer 3

Probablemente deberíamos comenzar con un límite superior aproximado: al expandir esta expresión obtendrá un polinomio de grado [matemático] 13 \ cdot 100, [/ matemático] por lo que tiene como máximo [matemático] 1301 [/ matemático] términos.

Como señaló el usuario, necesitamos contar el número de valores diferentes de la expresión [math] 13i + 7j [/ math] toma para [math] i, j \ geq 0 [/ math] y [math] i + j \ le 100. [/ math]

Imagine que descartamos las dos últimas condiciones y simplemente asumimos que [matemática] i, j \ in \ mathbb {Z}. [/ Matemática] Entonces porque [matemática] 7 [/ matemática] y [matemática] 13 [/ matemática] son ​​relativamente primos , obtendríamos cualquier número entero como la combinación lineal entera [matemáticas] 13i + 7j [/ matemáticas].

La situación será un poco peor si requerimos [matemática] i, j \ ge 0: [/ matemática] Podremos obtener cualquier número entero positivo a partir de cierta [matemática] b \ in \ mathbb {N} [/ matemática] , aunque habrá huecos en los enteros que sean más pequeños que [math] b [/ math].

Ser más preciso:

Proposición 1 . Sea [math] i, j \ geq 0. [/ math] Entonces [math] 13i + 7j [/ math] toma cualquier valor entero positivo mayor o igual a [math] 6 \ cdot 13 = 78 [/ math] para apropiadamente elegido [math] i, j \ in \ mathbb {N} _0 [/ math].

Prueba . Observe que [matemáticas] 1 = 2 \ cdot 7 -13 \; (*). [/ Matemáticas]

Deje [math] n \ ge 6 \ cdot 13. [/ math] Entonces podemos escribir [math] n = 6 \ cdot 13 + a + 7k, [/ math] donde [math] 0 \ le a \ le 6 [ / math] y [math] k \ in \ mathbb {N} _0. [/ math] Al conectar para [math] 1 [/ math] la expresión (*) vemos:

[matemáticas] n = 6 \ cdot 13 + a (2 \ cdot 7-13) + 7k = (2a + k) \ cdot 7 + (6-a) \ cdot 13. [/ math]

Por lo tanto, puede ver que [math] n [/ math] puede expresarse como una combinación lineal entera de [math] 7 [/ math] y [math] 13 [/ math] con coeficientes no negativos. [matemáticas] \ blacksquare [/ matemáticas]

Bueno, esta es una buena noticia. Pero también tenemos que lidiar con la restricción [matemáticas] i + j \ leq 100 [/ matemáticas] que nos impide obtener grandes exponentes (cerca de [matemáticas] 1300 [/ matemáticas]) de manera contigua.

Bueno, podemos reescribir [matemáticas] (x ^ {13} + x ^ 7 + 1) ^ {100} [/ matemáticas] como [matemáticas] x ^ {1300} (1 + x ^ {- 6} + x ^ {-13}) ^ {100}. [/ Math] Ahora sustituyendo [math] u = x ^ {- 1} [/ math] verá que los poderes superiores de la expresión original corresponden a los poderes inferiores de [math] ( 1 + u ^ {6} + u ^ {13}) ^ {100}. [/ Math]

Obviamente, podemos formular la proposición análoga a la Proposición 1 usando que [math] 13 -2 \ cdot 6 = 1. [/ Math]

Proposición 2. Sea [math] i, j \ in \ mathbb {N} _0. [/ Math] Entonces [math] 13i + 6j [/ math] toma cualquier valor entero positivo mayor o igual a [math] 10 \ cdot 6 = 60. [/ Matemáticas]

Prueba. Deje [math] n \ ge 10 \ cdot 6. [/ Math]

Escriba [math] n = 10 \ cdot 6 + a + 6k, [/ math] donde [math] 0 \ le a \ le 5 [/ math] es el resto de la división de [math] n -60 [/ math] por [matemática] 6 [/ matemática] y [matemática] k \ in \ mathbb {N} _0 [/ matemática] es el cociente de esta división.

Tenga en cuenta que [math] a = 13a-2a \ cdot 6. [/ Math]

Entonces [matemáticas] 10 \ cdot 6 + a + 6k = 10 \ cdot 6 + 13a -2a \ cdot 6 + 6k = 13a + (10-2a + k) \ cdot 6. [/ Math]

Entonces [math] n [/ math] es una combinación entera no negativa de [math] 13 [/ math] y [math] 6. [/ Math] [math] \ blacksquare [/ math]

La combinación de estas dos proposiciones lleva a la siguiente solución.

Obtendremos todos los términos con exponentes en el rango [math] 6 \ cdot 13, \ ldots, 1300 – 6 \ cdot 10, [/ math] un total de [math] 1163 [/ math] términos. Después de eso, tenemos que calcular el número de exponentes de la forma [matemáticas] 13i + 7j [/ matemáticas] menos que [matemáticas] 78 [/ matemáticas] y el número de exponentes de la forma [matemáticas] 13i + 6j [/ matemáticas ] menos de [matemáticas] 60 [/ matemáticas] a mano:

Así obtenemos un total de [matemáticas] 1163 + (12 +10 +8 +6 +4 +2) + (10 +8 +6 +4 +2) = 1235 [/ matemáticas] términos.

Answer 4

En Mathematica

> Longitud [ [correo electrónico protegido] @Expand [(x ^ 13 + x ^ 7 + 1) ^ 100]]
1235

Wolfram alpha también funciona: Expandir [(x ^ 13 + x ^ 7 + 1) ^ 100] – Wolfram | Alpha