Given two integers $N$ and $M$ , How to find out number of arrays A of size N, such that :
- Each of the element in array, $1 ≤ A[i] ≤ M$
For each pair i, j ($1 ≤ i < j ≤ N$)
$GCD(A[i], A[j]) = 1$
$M$ can be at max $100$. But $N$ can be upto $100000$. Is there some direct mathematical formula for the same ?
Example to make question clear : Say $N=3$ and $M=3$ then answer is $13$.
Not exactly an answer. I guess this is sort of a programming question.
Note that non-one terms in the array is very few. If the non-one terms are all primes, for $M=100$, there are at most $25$ of them. If there are not even prime $like 6$, it is even less, since $6$ takes two primes, reducing the number of possible non-one terms.
Then it remains to count the number of combination of coprime non-one terms with $k$ elements, where $0\leq k \leq 25$.
For example, with $N=5$, $k=2$, we have $(2,3), (2,5), (3,5), (3,4), (4,5)$. Then what we need is just permute them, and add $1$'s between them. Then we have $5$ combinations of coprime non-one terms with $k=2$ elements (I know that term is not very precise. But it basically means the number of combination of $k$ integers s.t. they are at least one, and they are coprime). Then we permute them. For example for $(2,3)$, we can obtain two permutations, which are $(2,3)$ and $(3,2)$ (Well, another bad notation). Then we add $1$'s to the permutations. They are $(1,2,3), (2,1,3), (2,3,1), (1,3,2), (3,1,2), (3,2,1).$
For example, with $N=M=3$, there is one combination for zero non-one term, which is empty set. For $k=1$, there are two combinations, namely $2$ and $3$. For $k=2$, we have $(2,3)$. Permuting them, and add $1$'s, we have $13$