0
$\begingroup$

Given $a,b,c,s\in\Bbb N$ such that $(a,b,c)=1$ with promise that we have at most one triple $x,y,z\in\Bbb N$ such that $ax+by+cz=s$, what is a good algorithm that runs in $O(\log(abcs))$ time to find such a triple or return empty?

I am trying to use FrobeniusSolve as recommended in the comments in this accepted answer here Frobenius number for three numbers. However it seems pretty slow (that is does not seem logarithmic in $abcs$).

What is the complexity of this method that is implemented in $\mathsf{mathematica}$? Is there an $O(\log(abcs))$ time complexity method or something close to it?

$\endgroup$
1
$\begingroup$

It is almost the Frobenius problem for three variables, where many results are known. Modifying your equation as $$ax_1+bx_2+cx_3=n,$$ where $x_i\geq 0$ and $n=s-a-b-c$ yields a Frobenius problem. See this related mathoverflow link: Frobenius number for three numbers. Mathematica has a procedure to determine all solutions: FrobeniusSolve.

$\endgroup$
  • $\begingroup$ pardon me but these seem to be talking about Frobenius number calculation. I actually want to find $(x,y,x)\in\Bbb N^3$. Do these algorithms do that in $O(\log(abcs))$ time? Could you post the correct paper? $\endgroup$ – user76479 Aug 23 '15 at 21:16
  • $\begingroup$ See Pete L. Clark's answer: [mathoverflow.net/a/23155/74606]. Greenberg provided an algorithm using only $O(\log a)$ steps to generate a nonnegative solution of the linear Diophantine equation $ax_1+bx_2+cx_3=n$. $\endgroup$ – castor Aug 24 '15 at 1:01
  • $\begingroup$ I saw that too and the paper. What is a 'step'? What is total arithmetic operations? Is each step $O(\log(abcs))$ arithmetic operations? $\endgroup$ – user76479 Aug 24 '15 at 2:18
  • $\begingroup$ What kind of timings have you obtained? Since you have the promise to have at most one solution you should try FrobeniusSolve[{a,b,c},n,1]. $\endgroup$ – castor Aug 24 '15 at 6:12
  • $\begingroup$ E.g. FrobeniusSolve[{12111139,13573321,29991743},29999999980,1] takes less than a second to find $x_1=619, x_2=1543, x_3=52.$ $\endgroup$ – castor Aug 24 '15 at 6:27

Your Answer

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