Skip to Main content Skip to Navigation
Conference papers

On the Frobenius’ Problem of three numbers

Abstract : Given $k$ natural numbers $\{a_1, \ldots ,a_k\} \subset \mathbb{N}$ with $1 \leq a_1 < a_2 < \ldots < a_k$ and $\mathrm{gcd} (a_1, \ldots ,a_k)=1$, let be $R(a_1, \ldots ,a_k) = \{ \lambda_1 a_1+ \cdots + \lambda_k a_k | \space \lambda_i \in \mathbb{N}, i=1 \div k\}$ and $\overline{R}(a_1, \ldots ,a_k) = \mathbb{N} \backslash R (a_1, \ldots ,a_k)$. It is easy to see that $| \overline{R}(a_1, \ldots ,a_k)| < \infty$. The $\textit{Frobenius Problem}$ related to the set $\{a_1, \ldots ,a_k\}$ consists on the computation of $f(a_1, \ldots ,a_k)=\max \overline{R} (a_1, \ldots ,a_k)$, also called the $\textit{Frobenius number}$, and the cardinal $| \overline{R}(a_1, \ldots ,a_k)|$. The solution of the Frobenius Problem is the explicit computation of the set $\overline{R} (a_1,\ldots ,a_k)$. In some cases it is known a sharp upper bound for the Frobenius number. When $k=3$ this bound is known to be $$F(N)=\max\limits_{\substack{0 \lt a \lt b \lt N \\ \mathrm{gcd}(a,b,N)=1}} f(a,b,N)= \begin{cases} 2(\lfloor N/2 \rfloor -1)^2-1 & \textrm{if } N \equiv 0 (\mod 2),\\ 2 \lfloor N/2 \rfloor (\lfloor N/2 \rfloor -1) -1 & \textrm{if } N \equiv 1 (\mod 2).\\ \end{cases}$$ This bound is given in [Dixmier1990]. In this work we give a geometrical proof of this bound which allows us to give the solution of the Frobenius problem for all the sets $\{\alpha ,\beta ,N\}$ such that $f(\alpha ,\beta ,N)=F(N)$.
Complete list of metadata

Cited literature [7 references]  Display  Hide  Download

https://hal.inria.fr/hal-01184451
Contributor : Coordination Episciences Iam <>
Submitted on : Monday, August 17, 2015 - 10:48:51 AM
Last modification on : Monday, November 16, 2020 - 3:56:03 PM
Long-term archiving on: : Wednesday, November 18, 2015 - 10:35:39 AM

File

dmAE0162.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01184451, version 1

Collections

Citation

Francesc Aguiló, Alícia Miralles. On the Frobenius’ Problem of three numbers. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. pp.317-322. ⟨hal-01184451⟩

Share

Metrics

Record views

269

Files downloads

794