On the Frobenius’ Problem of three numbers
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,...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2005-01-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/3462/pdf |
| _version_ | 1827324061312614400 |
|---|---|
| author | Francesc Aguiló Alícia Miralles |
| author_facet | Francesc Aguiló Alícia Miralles |
| author_sort | Francesc Aguiló |
| collection | DOAJ |
| description | 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)$. |
| first_indexed | 2024-04-25T02:02:45Z |
| format | Article |
| id | doaj.art-40c611e2ceae41e7a9c04aab1bda7e96 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T02:02:45Z |
| publishDate | 2005-01-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-40c611e2ceae41e7a9c04aab1bda7e962024-03-07T14:41:16ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502005-01-01DMTCS Proceedings vol. AE,...Proceedings10.46298/dmtcs.34623462On the Frobenius’ Problem of three numbersFrancesc Aguiló0Alícia Miralles1Departament of Matemàtica Aplicada IV Mathematics Applied to CryptographyDepartament of Matemàtica Aplicada IV Mathematics Applied to CryptographyGiven $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)$.https://dmtcs.episciences.org/3462/pdfminimum distance diagramsmith normal forml-shaped tilefrobenius problem[info.info-dm] computer science [cs]/discrete mathematics [cs.dm][math.math-co] mathematics [math]/combinatorics [math.co][info.info-hc] computer science [cs]/human-computer interaction [cs.hc] |
| spellingShingle | Francesc Aguiló Alícia Miralles On the Frobenius’ Problem of three numbers Discrete Mathematics & Theoretical Computer Science minimum distance diagram smith normal form l-shaped tile frobenius problem [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] [math.math-co] mathematics [math]/combinatorics [math.co] [info.info-hc] computer science [cs]/human-computer interaction [cs.hc] |
| title | On the Frobenius’ Problem of three numbers |
| title_full | On the Frobenius’ Problem of three numbers |
| title_fullStr | On the Frobenius’ Problem of three numbers |
| title_full_unstemmed | On the Frobenius’ Problem of three numbers |
| title_short | On the Frobenius’ Problem of three numbers |
| title_sort | on the frobenius problem of three numbers |
| topic | minimum distance diagram smith normal form l-shaped tile frobenius problem [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] [math.math-co] mathematics [math]/combinatorics [math.co] [info.info-hc] computer science [cs]/human-computer interaction [cs.hc] |
| url | https://dmtcs.episciences.org/3462/pdf |
| work_keys_str_mv | AT francescaguilo onthefrobeniusproblemofthreenumbers AT aliciamiralles onthefrobeniusproblemofthreenumbers |