Timeline for Frobenius number for three numbers
Current License: CC BY-SA 2.5
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 21, 2010 at 21:59 | comment | added | Stan Wagon | Sorry -- I might have erred in my thoughts on Rodseth. And, yes, I said "n" where I mean log N. Reviewing our INTEGERS paper (INTEGERS, 7 (2007) #A15, 63 pp. <integers-ejcnt.org/vol7.html>), I see that our section 5 goes into a lot of details on the n=3 case: We use ideas of Eisenbrand-Rote for some speedups. But overall complexity is still softly linear. Seems a little more complicated than just an extended GCD. | |
| Dec 19, 2010 at 6:46 | comment | added | Alexey Ustinov | It is strange, because for $n=3$ Rodseth is just extended GCD algorithm. In the worst case it requares $O(\log^2 N)$ operations (and it is known that comlexity can be reduced to $O(\log^{1+\epsilon} N)$). Is your algorithm faster? | |
| Dec 18, 2010 at 16:02 | comment | added | Stan Wagon | Mathematica does not use Rodseth. It uses the very fast algorithm described in our paper in INTEGERS and cited in my answer. This works even for 10000-digit or longer numbers. I believe the algorithm's complexity is "softly linear": O(n^(1+epsilon)). THe specific case of n = 3 is discussed in detail in our paper. Stan Wagon | |
| May 22, 2010 at 12:27 | vote | accept | Jernej | ||
| May 5, 2010 at 4:38 | history | edited | Alexey Ustinov | CC BY-SA 2.5 |
added 128 characters in body
|
| May 4, 2010 at 11:36 | comment | added | Alexey Ustinov | For example $f(6,10,15)=2f(3,5,15)=6f(1,5,5)=30f(1,1,1)=60$, $g(6,10,15)=60-6-10-15=29$. | |
| May 4, 2010 at 11:33 | comment | added | Alexey Ustinov | First of all you must use Johnson's formula. For modified Frobenius number $f(a,b,c)=g(a,b,c)+a+b+c$ it gives $f(a,b,c)=d f(a/d,b/d,c)$. It allows to reduce calculation of $f(a,b,c)$ to the case $(a,b)=(a,c)=(b,c)=1$. | |
| May 1, 2010 at 14:18 | comment | added | Jernej | The algorithm can be found here: books.google.com/… The first line of the algorithm computes $s_0$ such that $s_0a_2 = a_3 \mod a_1$ given $1 \leq a_1 < a_2 <a_3$ such that $gcd(a_1,a_2,a_3) = 1$. Am I missing something or is not always possible to compute $s_0$? For example for $6,10,15$? | |
| May 1, 2010 at 13:59 | vote | accept | Jernej | ||
| May 1, 2010 at 20:56 | |||||
| May 1, 2010 at 9:24 | history | answered | Alexey Ustinov | CC BY-SA 2.5 |