Contar matrices con cada uno de los elementos de la matriz coprime por pares

Question

Dados dos enteros $N$ et $M$ Cómo averiguar el número de matrices A de tamaño N, tales que :

1. Cada uno de los elementos del array, $1 A[i] M$

2. Para cada par i, j ( $1 i < j N$ )

   $GCD(A[i], A[j]) = 1$

$M$ puede estar al máximo $100$ . Pero $N$ puede ser de hasta $100000$ . ¿Existe alguna fórmula matemática directa para ello?

Ejemplo para aclarar la pregunta: Digamos $N=3$ et $M=3$ entonces la respuesta es $13$ .

Answer 1

No es exactamente una respuesta. Supongo que esto es una especie de pregunta de programación.

Tenga en cuenta que los términos que no son uno en la matriz son muy pocos. Si los términos no-uno son todos primos, para $M=100$ hay a lo sumo $25$ de ellos. Si ni siquiera hay primos $like 6$ es aún menor, ya que $6$ toma dos primos, reduciendo el número de posibles términos no uno.

Luego queda contar el número de combinaciones de términos coprimos no uno con $k$ elementos, donde $0\leq k \leq 25$ .

Por ejemplo, con $N=5$ , $k=2$ tenemos $(2,3), (2,5), (3,5), (3,4), (4,5)$ . Entonces lo que necesitamos es simplemente permutarlos, y añadir $1$ entre ellos. Entonces tenemos $5$ combinaciones de términos coprimos no uno con $k=2$ elementos (sé que este término no es muy preciso. Pero básicamente significa el número de combinaciones de $k$ enteros siempre que sean al menos uno y sean coprimos). Entonces los permutamos. Por ejemplo, para $(2,3)$ podemos obtener dos permutaciones, que son $(2,3)$ et $(3,2)$ (Bueno, otra mala anotación). Entonces añadimos $1$ a las permutaciones. Son $(1,2,3), (2,1,3), (2,3,1), (1,3,2), (3,1,2), (3,2,1).$

Por ejemplo, con $N=M=3$ , hay una combinación para el término cero no uno, que es el conjunto vacío. Para $k=1$ Hay dos combinaciones, a saber $2$ et $3$ . Para $k=2$ tenemos $(2,3)$ . Permutarlas, y añadir $1$ 's, tenemos $13$