6
$\begingroup$

The Diophantine equation of Frobenius is any equation of the form:

$$\sum_{i=1}^k a_i x_i = n$$ where the $a_i$'s are given and so are $k$ and $n$.

I'm looking for an algorithm to compute the number of solutions in non-negative integers to such equation. Given as input an array of the $a_i$'s and $n$, I need the algorithm to produce me the AMOUNT of solutions to the equation, regardless of what the solutions are. I've searched all over the internet (literally), including this site and https://stackoverflow.com/. I have found many articles about it and similiar questions, and all of which I've read, but I have not found particularly what I'm looking for. The most "useful" article I've found is : http://sertoz.bilkent.edu.tr/papers/froben.pdf which provides an explicit formula at the very end. However, with the lack of mathematical knowledge and recognition of the notations, due to me not being a student of mathematics/combinatorics, I cannot compute the algorithm to the formula, nor be sure it's really "explicit" and simple.

I found a book with which i've gotten this far (read over 100 pages), which provides explicit formulas for such solutions but for very simple diophantine equations. Whether or not formulas exist for larger $k$'s (up to 20) and $n$'s (up to 5000), I know FOR SURE these equations can be solved algorithmically and efficiently, as I know of (very very few) people who have done so. I've also tried to create such efficient algorithm myself but to no avail.

So.. I guess that's it. If you can provide me with some insights/formulas/algorithms (if in Java then even better) then I would be.. Unspeakably happy and grateful for this.

Thanks a lot in advance, Matan.

|cite|improve this question
$\endgroup$
  • $\begingroup$ I know someone who is very interested in this specific topic and is probably willing to talk to discuss it with you. $\endgroup$ – Zubin Mukerjee Mar 9 '15 at 13:13
  • $\begingroup$ @ZubinM Sure, would be happy to discuss this. My email is Matanatzz@gmail.com and Skype is: Matanhey. How can i contact him? $\endgroup$ – Matan Mar 9 '15 at 13:42
  • $\begingroup$ @ZubinMukerjee If there is some communication on this regard, please make it known, as it is a very deserving topic. $\endgroup$ – jiten Dec 24 '17 at 1:00
1
$\begingroup$

If the $a$'s are positive integers, there's a straightforward solution to your question that involves generating functions. The number of solutions to your equation is $[x^n]\prod_i(1-x^{a_i})^{-1}$. However, since you say you're not a "student of combinatorics", you'll probably have to learn about generating functions for this answer to make any sense. There are lots of good books on the subject. My favorite is this.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I have just downloaded the book and started reading it. Can you, however, please further explain your solution? You omitted the subscripts from the $x$'s. I'm pretty sure that's not a mistake, but what is it then? Please further explain this whole function. And thank you very much for replying :) @RusM $\endgroup$ – Matan Mar 10 '15 at 19:54

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.