3 votos

¿Cómo se calcula el GCD?

¿Cómo evaluar lo siguiente con la ayuda de la función Mobius?

$$\displaystyle\sum_{i=1}^n \sum_{j=i+1}^n \sum_{k=j+1}^n \sum_{l=k+1}^n {gcd(i,j,k,l)^4} .$$

En otras palabras, tenemos que seleccionar todos los cuatrillizos posibles de (1 ton n), y luego sumar su valor con la potencia 4.

Ejemplo:-

N=4 :

(1,2,3,4) : gcd(1,2,3,4)^4 = 1

Suma total = 1

Para el segundo caso, dejemos que N=5 :

(1,2,3,4) : gcd(1,2,3,4)^4 = 1

(1,2,3,5) : gcd(1,2,3,5)^4 = 1

(1,2,4,5) : gcd(1,2,4,5)^4 = 1

(1,3,4,5) : gcd(1,3,4,5)^4 = 1

(2,3,4,5) : gcd(2,3,4,5)^4 = 1

Suma total = 1+1+1+1+1 = 5.

Mi enfoque es: Calcular el número de cuatrillos con gcd=2,3,4,...hasta n.

Digamos que el número de cuatrillos con gcd=2 son x1, para gcd=3, es x2...y así sucesivamente.

Ahora, l = $$\binom{n}{4}$$ -(x1+x2+.......xn-1) = número de cuatrillos con gcd=1.

Ahora, la respuesta final = l^4+x1^4+x2^4+.....

El único problema que tengo es ¿cómo calcular el número de cuatrillizos con gcd=x con la ayuda de la función mobius?

3voto

metamorphy Puntos 186

Consideremos los conjuntos de cuádruples de números enteros $$Q(n)=\{(i,j,k,l) : 1\leqslant i<j<k<l\leqslant n\},\\ Q(n,d)=\{(i,j,k,l)\in Q(n) : \gcd(i,j,k,l)=d\}$$ para $1\leqslant d\leqslant n$ . Es evidente que tenemos $$|Q(n)|=\binom{n}{4},\quad Q(n)=\bigcup_{d=1}^{n}Q(n,d),\quad Q(n,d)=dQ(\lfloor n/d\rfloor,1)$$ (donde, para el último, $d(i,j,k,l):=(di,dj,dk,dl)$ y $dS:=\{ds : s\in S\}$ se suponen).

Esto significa que si $F(n)=|Q(n,1)|$ entonces $|Q(n,d)|=F(\lfloor n/d\rfloor)$ y $$\color{blue}{\sum_{d=1}^{n}F(\lfloor n/d\rfloor)=\binom{n}{4}}\quad\implies\quad F(n)=\sum_{d=1}^{n}\mu(d)\binom{\lfloor n/d\rfloor}{4}$$ por Inversión de Möbius . La suma que necesitamos es $S(n)=\sum\limits_{d=1}^{n}d^4 F(\lfloor n/d\rfloor)$ . Para calcularla, se puede evitar el cálculo de $\mu$ utilizando la ecuación "azul" anterior como recurrencia para $F(n)$ y la agrupación de términos con igual $\lfloor n/d\rfloor$ (aquí están mis respuestas sugiriendo esto también: 1 , 2 , 3 ).

0 votos

Soy muy nuevo en el concepto de inversión de mobius. ¿Puedes explicar la parte de cómo calcular la última suma? ¿Y cuál es el significado de [n/d] significa la mayor función entera?

0 votos

La respuesta correcta para n=8 es 85 pero tu fórmula da 69 :(

0 votos

¿Qué se hace [n/d] es menos de 4?

0voto

Hagen von Eitzen Puntos 171160

Un cuadruplete con gcd un múltiplo de $d$ se produce si todos los $i,j,k,l$ son múltiplos de $d$ para lo cual hay ${\lfloor n/d\rfloor\choose d}$ posibilidades. Así llegarás a $${n\choose 4}\cdot 1^4+{\lfloor n/2\rfloor\choose 4}\cdot (2^4-1^4) +{\lfloor n/3\rfloor\choose 4}\cdot (3^4-1^4)+{\lfloor n/4\rfloor\choose 4}\cdot (4^4-2^4)+\cdots$$

3 votos

Deberías dar una fórmula para el término general, ya que no está claro para alguien que no sepa la respuesta.

0 votos

@GregMartin ¿Puedes explicar la respuesta con un poco más de detalle y darme la fórmula general?

0 votos

@Hagen von Eitzen Para n=6, la respuesta es 15, y tu fórmula da la respuesta como '5'. Es incorrecto.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X