Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2312.15227 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913599776096256 |
|---|---|
| author | Williams, Aled Haijima, Daiki |
| author_facet | Williams, Aled Haijima, Daiki |
| contents | In this paper we study the (classical) Frobenius problem, namely the problem of finding the largest integer that cannot be represented as a nonnegative integral combination of given relatively prime (strictly) positive integers (known as the Frobenius number). The main contribution of this paper are observations regarding a previously known upper bound on the Frobenius number where, in particular, we observe that a previously presented argument features a subtle error, which alters the value of the upper bound. Despite this, we demonstrate that the subtle error does not impact upon on the validity of the upper bound, although it does impact on the upper bounds tightness. Notably, we formally state the corrected result and additionally compare the relative tightness of the corrected upper bound with the original. In particular, we show that the updated bound is tighter in all but only a relatively "small" number of cases using both formal techniques and via Monte Carlo simulation techniques. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_15227 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Considering a Classical Upper Bound on the Frobenius Number Williams, Aled Haijima, Daiki Number Theory Optimization and Control 11D04, 90C10, 11D45 In this paper we study the (classical) Frobenius problem, namely the problem of finding the largest integer that cannot be represented as a nonnegative integral combination of given relatively prime (strictly) positive integers (known as the Frobenius number). The main contribution of this paper are observations regarding a previously known upper bound on the Frobenius number where, in particular, we observe that a previously presented argument features a subtle error, which alters the value of the upper bound. Despite this, we demonstrate that the subtle error does not impact upon on the validity of the upper bound, although it does impact on the upper bounds tightness. Notably, we formally state the corrected result and additionally compare the relative tightness of the corrected upper bound with the original. In particular, we show that the updated bound is tighter in all but only a relatively "small" number of cases using both formal techniques and via Monte Carlo simulation techniques. |
| title | Considering a Classical Upper Bound on the Frobenius Number |
| topic | Number Theory Optimization and Control 11D04, 90C10, 11D45 |
| url | https://arxiv.org/abs/2312.15227 |