¿Número de formas de dividir un conjunto de números en 2 conjuntos tales que el DGC de su producto sea 1?

Question

Dado un conjunto cualquiera de números enteros positivos, estoy tratando de encontrar una manera de dividir el conjunto en 2 partes tal que el gcd (máximo común divisor) del producto de los 2 conjuntos sea 1.

Conjunto de ejemplos :-

{2,3,5}

Camino(1):- (2,3) y (5) como gcd(6,5)=1

Camino(2):- (5) y (2,3) como gcd(5,6)=1

Camino(3):- (2,5) y (3) como gcd(10,3)=1

Camino(4):- (3) y (2,5) como gcd(3,10)=1

Camino(5):- (3,5) y (2) como gcd(15,2)=1

Camino(6):- (2) y (3,5) como gcd(2,15)=1

Por lo tanto, el número total de formas = 6 .

Estoy buscando un algoritmo/enfoque/fórmula corta (de forma cerrada) eficiente para resolver este problema.

Voy a añadir mi enfoque a este problema en breve.

Answer 1

No has especificado que cada conjunto debe tener al menos un elemento, por lo que hay dos particiones más, $\emptyset$ y $(2,3,5)$ y $(2,3,5)$ y $\emptyset$ , haciendo que $8$ . Es tradicional considerar que el producto vacío es $1$ . Si ningún par de números tiene un factor común, como en este caso, se puede elegir cualquier subconjunto para el primer conjunto, y todos los demás forman el segundo conjunto. Para $3$ elementos que hay $2^3=8$ subconjuntos.

Si cualquier par de números comparte un factor común, tienen que ir en el mismo subconjunto. Si los números fueran $2,3,4,5$ tendrías que mantener $2$ y $4$ juntos, por lo que se obtendría el mismo $8$ soluciones como las anteriores, añadiendo $4$ en cualquier conjunto que contenga $2$ .

Puedes formar una cadena de elementos que tienen que ir juntos. Si sus números fueran $6,1523,29,35$ tendría que tener $6$ y $15$ juntos o ambos conjuntos tendrían un factor $3$ en su producto. Entonces hay que tener $35$ con ellos o ambos conjuntos tendrán un factor $5$ en su producto. Finalmente puede poner $23,29$ en cualquier lugar, por lo que tendrá $8$ soluciones.

Esto da el esquema de un algoritmo. Revisa los pares, viendo si tienen un factor común. Cualquier par que tenga un factor común se agrupa. Si encuentras un factor común con un número que ya ha sido agrupado con otros, todos van en el grupo. Finalmente, habrás dividido tus números en grupos disjuntos en los que ningún número de grupos diferentes tiene un factor común. Elige un subconjunto cualquiera de los grupos para el primer conjunto y el resto para el segundo. Puedes hacer esto en $2^{\text{number of groups}}$ maneras. Si no quieres las soluciones en las que un conjunto está vacío, resta $2$ .

Answer 2

Dejemos que $S$ sea su conjunto de enteros. Defina una relación $\sim$ en $S$ tal que $a\sim b$ si $\gcd(a,b)>1$ para todos $a,b\in S$ . Esta relación es reflexiva y simétrica, pero no necesariamente transitiva, por lo que $\approx$ sea el cierre transitivo de $\sim$ . (En breve describiré lo que esto significa en un ejemplo, así que no te estreses si no estás familiarizado con el cierre transitivo). $\approx$ es una relación de equivalencia, por lo que induce una partición en $S$ tal que $a$ y $b$ están en la misma parte de la partición si $a\approx b$ . Si hay $N$ partes de esa partición, entonces la respuesta a su pregunta es $2^N-2$ (o eso dividido por 2 si no quieres contar $\{2,3\}$ y $\{5\}$ como una disposición diferente a $\{5\}$ y $\{2,3\}$ . (Hay que restar $2$ porque los casos en los que un lado está "vacío" no deberían contar).

Por ejemplo, digamos que $S=\{2, 3, 4, 5, 6,7, 8,9,11,25$ }. Así, por ejemplo, $2\sim 6$ y $3\sim 6$ . No es el caso que $2\sim 3$ pero queremos estar seguros de que $2\approx 3$ porque $2$ y $3$ necesita estar en la misma parte que $6$ . (Eso es lo que quiero decir con cierre transitivo.) Así que la partición inducida por $\approx$ en $S$ es $\{\{2,3,4,6,8,9\},\{5,25\},\{7\},\{11\}\}$ . Esa partición tiene $4$ partes, por lo que hay $7$ esencialmente diferentes formas de partición $S$ (ou $14$ si se hace un doble recuento como en el enunciado del problema).