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?

Improve this question
$\endgroup$

1 Answer 1

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

Improve this answer
$\endgroup$
5
  • $\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
    Commented Aug 23, 2015 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
    Commented Aug 24, 2015 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
    Commented Aug 24, 2015 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
    Commented Aug 24, 2015 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
    Commented Aug 24, 2015 at 6:27

You must log in to answer this question.