7
$\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.

$\endgroup$
3
  • $\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, 2015 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, 2015 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, 2017 at 1:00

1 Answer 1

Reset to default
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.

$\endgroup$
1
  • $\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, 2015 at 19:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .