The Frobenius Number: Exploring The World Of Non-representable Integers
(2024) In Bachelor's Theses in Mathematical Sciences MATK11 20241Mathematics (Faculty of Engineering)
Mathematics (Faculty of Sciences)
Centre for Mathematical Sciences
- Abstract
- We call a number representable by some given integers $a_1,\dots,a_n$, if the number can be expressed as a linear combination of $a_1,\dots,a_n$ with non-negative coefficients. This thesis explores the properties of non-representable numbers, with the main focus on the greatest such number called the Frobenius number, denoted by $g(a_1,\dots,a_n)$. We derive a simple formula when $n=2$ for the Frobenius number, and for the number and sum of non-representable numbers. Furthermore, for $n=3$, we give exact formulae for some generalizations, and discuss the author's proposed corrected version of Tripathi's formula for the arbitrary case $g(a,b,c)$.
- Popular Abstract
- Imagine that you and your friends decided to go to a local fast food restaurant.
After some discussion, you arrive at the conclusion that together you would like to order and eat 43 chicken nuggets. The nuggets come in 3 sizes: a box of 6, 9 and 20 pieces. Since you are the mathematician of the group, you are given the great honor to do the math and place the order in the self-service machine. After some thought, you can get 42 and 44, but nothing seems to work for 43... Can it really be so? It turns out that 43 is the largest number that cannot be constructed with any multiples of 6, 9 and 20, which is what we call the Frobenius number (for 6,9 and 20). You start to think: Is this unique? Does this always happen? Is there always a... (More) - Imagine that you and your friends decided to go to a local fast food restaurant.
After some discussion, you arrive at the conclusion that together you would like to order and eat 43 chicken nuggets. The nuggets come in 3 sizes: a box of 6, 9 and 20 pieces. Since you are the mathematician of the group, you are given the great honor to do the math and place the order in the self-service machine. After some thought, you can get 42 and 44, but nothing seems to work for 43... Can it really be so? It turns out that 43 is the largest number that cannot be constructed with any multiples of 6, 9 and 20, which is what we call the Frobenius number (for 6,9 and 20). You start to think: Is this unique? Does this always happen? Is there always a largest number? Is there a formula for calculating this largest number?
This and other questions are explored in this thesis, with a surprising twist at the end. At first glance, this knowledge does not seem to be more than just a way to mess with a fast food restaurant employee, however, looking more deeply into the nature of this simple first-grade addition problem, many interesting patterns pop up. We explore not only the existence of the Frobenius number, but also the way we can easily calculate it for two chosen numbers, and not so easily calculate it for three. What about the other numbers that cannot be represented? Good question, look no further than Chapter 3, where we derive the formula for the amount of such numbers, and the formula for their sum.
Interestingly, we could approach this problem from the other way around as well: let us say you choose your favourite number, is there a double or triple for which your chosen number is the Frobenius number? The answer is yes! This and other interesting formulae are presented in Chapter 4, but uncharted territory awaits us at the end...
The Frobenius Formula for Three Numbers! In the final chapter, we discuss this with our focus on Tripathi's 2017 paper. However, the twist that I mentioned earlier is that computational evidence indicates that some of his proposed solutions are incorrect. We end this chapter with some computer-based predictions for corrected versions of Tripathi's results. Additionally, an algorithm is also presented at the end in order to enable one to double check their calculations.
And now, dear reader, you can go ahead and tell your friends more about why they should maybe consider getting more Chicken Nuggets the next time you are hungry... (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/student-papers/record/9150323
- author
- Suhajda, Péter LU
- supervisor
- organization
- alternative title
- The Frobenius Number
- course
- MATK11 20241
- year
- 2024
- type
- M2 - Bachelor Degree
- subject
- keywords
- Frobenius, Frobenius number, Frobenius number problem, postage stamp problem, coin change problem, coin change, non-representable numbers, representable, Tripathi, Tripathi's formula
- publication/series
- Bachelor's Theses in Mathematical Sciences
- report number
- LUNFMA-4161-2024
- ISSN
- 1654-6229
- other publication id
- 2024:K3
- language
- English
- id
- 9150323
- date added to LUP
- 2024-04-23 15:36:08
- date last changed
- 2024-04-23 15:36:08
@misc{9150323,
abstract = {{We call a number representable by some given integers $a_1,\dots,a_n$, if the number can be expressed as a linear combination of $a_1,\dots,a_n$ with non-negative coefficients. This thesis explores the properties of non-representable numbers, with the main focus on the greatest such number called the Frobenius number, denoted by $g(a_1,\dots,a_n)$. We derive a simple formula when $n=2$ for the Frobenius number, and for the number and sum of non-representable numbers. Furthermore, for $n=3$, we give exact formulae for some generalizations, and discuss the author's proposed corrected version of Tripathi's formula for the arbitrary case $g(a,b,c)$.}},
author = {{Suhajda, Péter}},
issn = {{1654-6229}},
language = {{eng}},
note = {{Student Paper}},
series = {{Bachelor's Theses in Mathematical Sciences}},
title = {{The Frobenius Number: Exploring The World Of Non-representable Integers}},
year = {{2024}},
}