Contar el número de soluciones positivas de una ecuación diofántica lineal

Question

Dada una ecuación lineal de Diophantine, ¿cómo puedo contar el número de soluciones positivas?

Más específicamente, me interesa el número de soluciones positivas para la siguiente ecuación lineal de Diophantine:

Unesdoc.unesco.org unesdoc.unesco.org

Actualización: sólo estoy interesado en soluciones diferentes de cero.

Answer 1

El número de soluciones de (algunos de expresión lineal) = n, es siempre algo que se parece a un polinomio (ver http://en.wikipedia.org/wiki/Ehrhart_polynomial) Usted puede calcular de forma recursiva o calcular lo suficientemente pequeños valores, por lo que se determina el polinomio.

Me deja hacer el método recursivo aquí. En primer lugar, es más fácil para mí para permitir $0$ como un valor, no estoy seguro de si lo permitimos, si no, entonces, por el cambio de las variables, es la misma como la búsqueda de una suma que da $40$ en lugar de $47$, lo que permite cosas como $x=0$ y, a continuación, la adición de $1$ a todo el mundo.

Para cualquier $n \ge 0$, el número de soluciones de $z=n$$P_1(n) = 1$.

Para cualquier $n \ge 0$, el número de soluciones de $y+z=n$$P_2(n) = P_1(n) + P_1(n-1) + \ldots P_1(0) = (n+1)*1 = n+1$.

Para cualquier $n \ge 0$, el número de soluciones de $2x+y+z=n$$P_3(n) = P_2(n) + P_2(n-2) + \ldots $. Empieza a ser difícil : tengo que separar dos casos accorging a la paridad de $n$ : $$ P_3(2m) = (2m+1) + (2m-1) + \ldots + (1) = (m+1)^2 = (n^2+4n+4)/4 $$ $$ P_3(2m+1) = (2m+2) + (2m) + \ldots + (2) = (m+1)(m+2) = (n^2+4n+3)/4$$

Para el último paso, usted tiene que dividir en 6 de los casos tan sólo haré lo que usted necesita : $$P_4(6m+4) = P_3(6m+4) + P_3(6m+1) + \ldots + P_3(1) = \Sigma_{k=0}^m P_3(6k+1) + P_3(6k+4) $$ $$ = \Sigma_{k=0}^m ((6k+1)^2 + 4(6k+1)+3 + (6k+4)^2 + 4(6k+4)+4)/4 = \Sigma_{k=0}^m 18k^2+27k+11 $$ $$ = 3m(m+1)(2m+1)+27m(m+1)/2+11(m+1) = (12m^3 + 45m^2 + 55m +22)/2 $$

Por lo $P_4(40) = P_4(6*6+4) = 2282$.

Answer 2

Deje $\mathbb{N} := \{0, 1, 2, ...\}$ ser el conjunto de los números naturales (i.e números enteros no negativos). Dado $N\in\mathbb{N}\backslash\{0\}$, $n\in\mathbb{N}$, y $(a_1, a_2, ..., a_N) \in\mathbb{N}^N$, vamos a $P_{N}(a_1, a_2, ..., a_N, n)$ el número de soluciones del sistema lineal Diophatine ecuación \begin{equation} \sum_{k=1}^N{a_kx_k} = n, \space x\in\mathbb{N}^N \end{equation}

Tenga en cuenta que $P_{N}$ define una función de$\mathbb{N}^{N+1}$$\mathbb{N}\backslash\{0\}$.

A continuación, la siguiente fórmula recursiva se establece fácilmente por inducción en $N$ ( $N>2$ , fix $x_1\in[0, n/a_1]\cap \mathbb{N}$, y para resolver $(x_2$, ..., $x_N)\in\mathbb{N}^{N-1}$) \begin{equation} \begin{split} P_1(a_1, n) = 1, \text{if %#%#% is a multiple of %#%#%, %#%#% otherwise;}\\ P_N(a_1, a_2, ..., a_N, n) = \sum_{x_1\in [0, n/a_1]\cap \mathbb{N}}P_{N-1}(a_2, ..., a_N, n - x_1a_1)\text{, if %#%#%} \end{split} \end{equation}

El siguiente (ingenuo) fragmento de código en Python va a resolver cualquier instancia del problema en un tiempo finito.

def diophantine_count(a, n):
"""Computes the number of nonnegative solutions (x) of the linear
Diophantine equation
    a[0] * x[0] + ... a[N-1] * x[N-1] = n

Theory: For natural numbers a[0], a[2], ..., a[N - 1], n, and j,
let p(a, n, j) be the number of nonnegative solutions.

Then one has:
    p(a, m, j) = sum p(a[1:], m - k * a[0], j - 1), where the sum is taken
    over 0 <= k <= floor(m // a[0])

Examples
--------
>>> diophantine_count([3, 2, 1, 1], 47)
3572
>>> diophantine_count([3, 2, 1, 1], 40)
2282
"""

def p(a, m, j):
    if j == 0:
        return int(m == 0)
    else:
        return sum([p(a[1:], m - k * a[0], j - 1)
                    for k in xrange(1 + m // a[0])])

return p(a, n, len(a))

Ahora que tenemos el martillo, vamos a encontrar las uñas...

OK, volviendo a tu problema, tenemos $n$.

N. B: $a_1$, de acuerdo con mercio de la fuerza bruta de cálculo :)

Saludos,