1
$\begingroup$

Consider a diophantine equation in n variables:
$a_1x_1+a_2x_2+...+a_nx_n=k$
All $a_i$'s, $x_i$'s and $k$ are restricted to non-negative integers $\mathbb{Z^+}$. (note that because of domain restrictions the number if solutions is guaranteed to be finite)
I need to generate a random solution to this equation and i do not know how to approach it. In other words i need an algorithm which is equally likely to generate any one of the possible solutions.
Any help would be welcome.

$\endgroup$
2
  • $\begingroup$ Do you just need a solution, or do you need an algorithm which is equally likely to produce any of the solutions? $\endgroup$ May 15, 2014 at 6:04
  • $\begingroup$ yes, i need an algorithm which is equally likely to produce any of the solutions. sorry if i was unclear. $\endgroup$ May 15, 2014 at 6:07

1 Answer 1

2
$\begingroup$

Let $f(a_1, a_2, \ldots, a_n, k)$ be the number of solutions. This is the coefficient of $x^k$ in the Maclaurin series $\prod_{j=1}^n (1 - x^{a_i})^{-1}$. The number of solutions with $x_1 = t$ is $f(a_2, \ldots, a_n, k - a_1 t)$ for $t = 0$ to $\lfloor k/a_1 \rfloor$. So choose $x_1$ with the probabilities $P(x_1 = t) = f(a_2,\ldots,a_n, k - a_1 t)/f(a_1,a_2,\ldots,a_n,k)$. Proceed recursively.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.