Contando el número de vectores enteros de Coprime N-dimensionales

Question

Estoy buscando una forma eficiente de contar el número de vectores de Coprimo en un conjunto finito y limitado de vectores enteros.

Los vectores en mi set son $ N $ -Dimensionales vectores enteros cuyos componentes están limitados en la parte superior e inferior por un valor arbitrario $ K $. Deje que $ x = [x_1, x_2, ldots, x_n] $ denote un vector de este conjunto. Entonces $ x $ es coprimo Si el mayor denominador común de todos sus elementos es 1. es decir, $ gcd (x_1, x_2, ..., x_n) = 1 $.

Algunos vectores de Coprime tridimensionales incluyen: $ x = [1,2, 3], [6, 10, 15], [0, 1, 1] $
Algunos vectores tridimensionales que no son de comprimencia incluyen: $ x = [2,4,6], [0, 10, 15], [0, 12, 12] $

Para $ n $ y $ k $, mi conjunto contiene un total de $ (2k+1)^n $ vectores enteros distintos ya que cada uno de los elementos $ n $ puede tomar valores enteros de $ -k, ldots, 0 , ldots, k $. Un enfoque de fuerza bruta para contar el número de vectores de Coprime consiste en iterar sobre cada uno de los $ (2k+1)^n $ posibles vectores y verificar para ver si son Coprime (usando, por ejemplo, por ejemplo, esta función). Desafortunadamente, este enfoque se encuentra rápidamente en problemas de tiempo y memoria para grandes valores de $ N $ y $ K $.

Me pregunto si alguien puede pensar en una forma de algoritmo inteligente para hacer esto. Idealmente, estoy buscando implementar este algoritmo como una función MATLAB que puede número de pares de Coprime dados $ N $ y $ K $ como su entrada.