Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Coin problem
open-in-new
<h2 id="statement">Statement</h2> <p>In mathematical terms, the problem can be stated: </p> Given positive <a href="/facts/Integer/PUwwrawx">integers</a> a 1 , a 2 , … , a n {\displaystyle a_{1},a_{2},\dots ,a_{n}} such that <a href="/facts/Greatest_common_divisor/kNFvBuKl">gcd</a> ( a 1 , a 2 , … , a n ) = 1 {\displaystyle (a_{1},a_{2},\dots ,a_{n})=1} , find the largest integer that <i>cannot</i> be expressed as an integer <a href="/facts/Conical_combination/41KGtqdd">conical combination</a> of these numbers, i.e., as a sum: k 1 a 1 + k 2 a 2 + ⋯ + k n a n {\displaystyle k_{1}a_{1}+k_{2}a_{2}+\dots +k_{n}a_{n}} where k 1 , k 2 , … , k n {\displaystyle k_{1},k_{2},\dots ,k_{n}} are non-negative integers. <p>This largest integer is called the Frobenius number of the set { a 1 , a 2 , … , a n } {\displaystyle \{a_{1},a_{2},\dots ,a_{n}\}} , and is usually denoted by g ( a 1 , a 2 , … , a n ) {\displaystyle g(a_{1},a_{2},\dots ,a_{n})} </p><p>The existence of the Frobenius number depends on the condition that the greatest common divisor (GCD) is equal to 1. Indeed, the potential sums are multiples of the GCD in all cases. Hence, if it is not 1, then there are always arbitrarily large numbers that cannot be obtained as sums. For example, if you had two types of coins valued at 6 cents and 14 cents, the GCD would equal 2, and there would be no way to combine any number of such coins to produce a sum which was an <a href="/facts/Parity_(mathematics)/7zq2UM4V">odd number</a>; additionally, <a href="/facts/Parity_(mathematics)/7zq2UM4V">even numbers</a> 2, 4, 8, 10, 16 and 22 (less than <i>m=24</i>) could not be formed, either. On the other hand, whenever the GCD equals 1, the set of integers that cannot be expressed as a conical combination of { a 1 , a 2 , … , a n } {\displaystyle \{a_{1},a_{2},\dots ,a_{n}\}} is <a href="/facts/Bounded_set/yCldjtoy">bounded</a> according to <a href="/facts/Schur%27s_theorem/2aJCkG2F">Schur's theorem</a>, and therefore the Frobenius number exists. </p> <h2 id="frobenius-numbers-for-small-n">Frobenius numbers for small <i>n</i></h2> <p>A closed-form solution exists for the coin problem only where <i>n</i> = 1 or 2. No closed-form solution is known for <i>n</i> > 2.<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> </p> <h3><i>n</i> = 1</h3> <p>If n = 1 {\displaystyle n=1} , then we must have a 1 = 1 {\displaystyle a_{1}=1} so that all natural numbers can be formed. </p> <h3><i>n</i> = 2</h3> <p>If n = 2 {\displaystyle n=2} , the Frobenius number can be found from the formula g ( a 1 , a 2 ) = a 1 a 2 − a 1 − a 2 {\displaystyle g(a_{1},a_{2})=a_{1}a_{2}-a_{1}-a_{2}} , which was discovered by <a href="/facts/James_Joseph_Sylvester/6NNurKJH">James Joseph Sylvester</a> in 1882.<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a><a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a> Sylvester also demonstrated for this case that there are a total of N ( a 1 , a 2 ) = ( a 1 − 1 ) ( a 2 − 1 ) / 2 {\displaystyle N(a_{1},a_{2})=(a_{1}-1)(a_{2}-1)/2} non-representable (positive) integers. </p><p>Another form of the equation for g ( a 1 , a 2 ) {\displaystyle g(a_{1},a_{2})} is given by Skupień<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a> in this proposition: If a 1 , a 2 ∈ N {\displaystyle a_{1},a_{2}\in \mathbb {N} } and gcd ( a 1 , a 2 ) = 1 {\displaystyle \gcd(a_{1},a_{2})=1} then, for each n ≥ ( a 1 − 1 ) ( a 2 − 1 ) {\displaystyle n\geq (a_{1}-1)(a_{2}-1)} , there is exactly one pair of nonnegative integers ρ {\displaystyle \rho } and σ {\displaystyle \sigma } such that σ < a 1 {\displaystyle \sigma <a_{1}} and n = ρ a 1 + σ a 2 {\displaystyle n=\rho a_{1}+\sigma a_{2}} . </p><p>The formula is proved as follows. Suppose we wish to construct the number n ≥ ( a 1 − 1 ) ( a 2 − 1 ) {\displaystyle n\geq (a_{1}-1)(a_{2}-1)} . Since gcd ( a 1 , a 2 ) = 1 {\displaystyle \gcd(a_{1},a_{2})=1} , all of the integers n − j a 2 {\displaystyle n-ja_{2}} for j = 0 , 1 , … , a 1 − 1 {\displaystyle j=0,1,\ldots ,a_{1}-1} are mutually distinct modulo a 1 {\displaystyle a_{1}} . Thus any integer m {\displaystyle m} must be congruent modulo a 1 {\displaystyle a_{1}} to one of these residues; in particular, taking m = a 1 {\displaystyle m=a_{1}} there is a unique value of j = σ ≥ 0 {\displaystyle j=\sigma \geq 0} and a unique integer t {\displaystyle t} , such that a 1 = n − σ a 2 + t a 1 {\displaystyle a_{1}=n-\sigma a_{2}+ta_{1}} . Rearranging, we have a nonnegative integer ρ = 1 − t {\displaystyle \rho =1-t} so that n = ρ a 1 + σ a 2 {\displaystyle n=\rho a_{1}+\sigma a_{2}} . Indeed, ρ ≥ 0 {\displaystyle \rho \geq 0} because ρ a 1 = n − σ a 2 ≥ ( a 1 − 1 ) ( a 2 − 1 ) − ( a 1 − 1 ) a 2 = − a 1 + 1 > ( − 1 ) a 1 {\displaystyle \rho a_{1}=n-\sigma a_{2}\geq (a_{1}-1)(a_{2}-1)-(a_{1}-1)a_{2}=-a_{1}+1>(-1)a_{1}} . </p><p>To show that exactly half of the integers 0 , 1 , … , a b − a − b {\displaystyle 0,1,\ldots ,ab-a-b} are representable as non-negative integer linear combinations, one first shows that if the integer k ∈ [ 0 , a b − a − b ] {\displaystyle k\in [0,ab-a-b]} is representable, then N − k {\displaystyle N-k} is not representable, where N = a b − a − b {\displaystyle N=ab-a-b} . </p><p>One then shows that the converse is true as well: if k {\displaystyle k} is not representable, then N − k {\displaystyle N-k} is representable. To show this, use the fact that gcd ( a , b ) = 1 {\displaystyle \gcd(a,b)=1} , which allows us to write k = x a + y b {\displaystyle k=xa+yb} . Reducing and re-arranging the coefficients by adding multiples of a b {\displaystyle ab} as necessary, we can assume 0 ≤ x < b {\displaystyle 0\leq x<b} (in fact, this x {\displaystyle x} is the unique such x {\displaystyle x} satisfying the equation and inequalities). </p><p>Similarly we take u , v {\displaystyle u,v} satisfying N − k = u a + v b {\displaystyle N-k=ua+vb} and 0 ≤ u < b {\displaystyle 0\leq u<b} . Now we can add these equations to write N = ( u + x ) a + ( y + v ) b {\displaystyle N=(u+x)a+(y+v)b} which, using N = a b − a − b {\displaystyle N=ab-a-b} yields a b − b ( 1 + y + v ) = a ( x + u + 1 ) {\displaystyle ab-b(1+y+v)=a(x+u+1)} . The integer x + u + 1 {\displaystyle x+u+1} is positive, because x , u ≥ 0 {\displaystyle x,u\geq 0} . In fact, since the left-hand side of a b − b ( 1 + y + v ) = a ( x + u + 1 ) {\displaystyle ab-b(1+y+v)=a(x+u+1)} is divisible by b {\displaystyle b} , and ( a , b ) = 1 {\displaystyle (a,b)=1} , we must have that x + u + 1 {\displaystyle x+u+1} is divisible by b {\displaystyle b} . Yet x , u ≤ b − 1 {\displaystyle x,u\leq b-1} , so x + u + 1 ≤ 2 b − 1 {\displaystyle x+u+1\leq 2b-1} , so that x + u + 1 = b {\displaystyle x+u+1=b} . Substituting this into a b − b ( 1 + y + v ) = a ( x + u + 1 ) {\displaystyle ab-b(1+y+v)=a(x+u+1)} and subtracting a b {\displaystyle ab} from both sides yields b ( 1 + y + v ) = 0 {\displaystyle b(1+y+v)=0} . So 1 + y + v = 0 {\displaystyle 1+y+v=0} . This implies that y + v = − 1 {\displaystyle y+v=-1} , which means that exactly one of y {\displaystyle y} or v {\displaystyle v} is negative. If y {\displaystyle y} is negative, then v ≥ 0 {\displaystyle v\geq 0} , which means that N − k = u a + v b {\displaystyle N-k=ua+vb} is representable; the case when v {\displaystyle v} is negative entails that k {\displaystyle k} is representable. </p><p>Thus for any non-negative integer k ∈ [ 0 , a b − a − b ] {\displaystyle k\in [0,ab-a-b]} , we know that exactly one of k {\displaystyle k} or ( a b − a − b ) − k {\displaystyle (ab-a-b)-k} is representable (and these are distinct, because a b − a − b {\displaystyle ab-a-b} must be odd as the integers a , b {\displaystyle a,b} are relatively prime). This shows that half of the integers in the given range are representable; since there are ( a b − a − b + 1 ) = ( a − 1 ) ( b − 1 ) {\displaystyle (ab-a-b+1)=(a-1)(b-1)} integers in the range [ 0 , a b − a − b ] {\displaystyle [0,ab-a-b]} , this gives the desired result. </p> <h3><i>n</i> = 3</h3> <p>Formulae<a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a> and fast algorithms<a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a> are known for three numbers though the calculations can be very tedious if done by hand. </p><p>Simpler lower and upper bounds for Frobenius numbers for <i>n</i> = 3 have also been determined. The asymptotic lower bound due to Davison </p> f ( a 1 , a 2 , a 3 ) ≡ g ( a 1 , a 2 , a 3 ) + a 1 + a 2 + a 3 ≥ 3 a 1 a 2 a 3 {\displaystyle f(a_{1},a_{2},a_{3})\equiv g(a_{1},a_{2},a_{3})+a_{1}+a_{2}+a_{3}\geq {\sqrt {3a_{1}a_{2}a_{3}}}} <p>is relatively sharp.<a class="footnote-ref" id="fnref:11" href="#fn:11"><sup>11</sup></a> ( f {\displaystyle f} here is the <i>modified Frobenius number,</i> which is the greatest integer not representable by <i>positive</i> integer linear combinations of a 1 , a 2 , a 3 {\displaystyle a_{1},a_{2},a_{3}} .) </p><p>The asymptotic average behaviour of f {\displaystyle f} for three variables is also known as:<a class="footnote-ref" id="fnref:12" href="#fn:12"><sup>12</sup></a> </p> f ( a 1 , a 2 , a 3 ) ∼ 8 π a 1 a 2 a 3 , {\displaystyle f(a_{1},a_{2},a_{3})\sim {\frac {8}{\pi }}{\sqrt {a_{1}a_{2}a_{3}}},} <h2 id="wilfs-conjecture">Wilf's conjecture</h2> <p>In 1978, Wilf conjectured that given coprime integers a 1 < a 2 < . . . < a d {\displaystyle a_{1}<a_{2}<...<a_{d}} , and their Frobenius number F {\displaystyle F} , we have </p> d ≥ F + 1 F + 1 − g , {\displaystyle d\geq {\frac {F+1}{F+1-g}},} <p>where g {\displaystyle g} denotes the number of all non-representable positive integers.<a class="footnote-ref" id="fnref:13" href="#fn:13"><sup>13</sup></a> In 2015, an asymptotic version of this was proven by Moscariello and Sammartano.<a class="footnote-ref" id="fnref:14" href="#fn:14"><sup>14</sup></a> </p> <h2 id="frobenius-numbers-for-special-sets">Frobenius numbers for special sets</h2> <h3>Arithmetic sequences</h3> <p>A simple formula exists for the Frobenius number of a set of integers in an <a href="/facts/Arithmetic_sequence/c4ew9Xoq">arithmetic sequence</a>.<a class="footnote-ref" id="fnref:15" href="#fn:15"><sup>15</sup></a> Given integers <i>a</i>, <i>d</i>, <i>w</i> with gcd(<i>a</i>, <i>d</i>) = 1: </p> g ( a , a + d , a + 2 d , … , a + w d ) = ( ⌊ a − 2 w ⌋ ) a + d ( a − 1 ) {\displaystyle g(a,a+d,a+2d,\dots ,a+wd)=\left(\left\lfloor {\frac {a-2}{w}}\right\rfloor \right)a+d(a-1)} <p>The n = 2 {\displaystyle n=2} case above may be expressed as a special case of this formula. </p><p>In the event that a > w 2 − 3 w + 1 {\displaystyle a>w^{2}-3w+1} , we can omit any subset of the elements a + 2 d , a + 3 d , . . . , a + ( w − 3 ) d , a + ( w − 2 ) d {\displaystyle a+2d,a+3d,...,a+(w-3)d,a+(w-2)d} from our arithmetic seq,e and the formula for the Frobenius number remains the same.<a class="footnote-ref" id="fnref:16" href="#fn:16"><sup>16</sup></a> </p> <h3>Geometric sequences</h3> <p>There also exists a closed form solution for the Frobenius number of a set in a <a href="/facts/Geometric_sequence/SVrkRHDX">geometric sequence</a>.<a class="footnote-ref" id="fnref:17" href="#fn:17"><sup>17</sup></a> Given integers <i>m</i>, <i>n</i>, <i>k</i> with gcd(<i>m</i>, <i>n</i>) = 1: </p> g ( m k , m k − 1 n , m k − 2 n 2 , … , n k ) = n k − 1 ( m n − m − n ) + m 2 ( n − 1 ) ( m k − 1 − n k − 1 ) m − n . {\displaystyle g(m^{k},m^{k-1}n,m^{k-2}n^{2},\dots ,n^{k})=n^{k-1}(mn-m-n)+{\frac {m^{2}(n-1)(m^{k-1}-n^{k-1})}{m-n}}.} A simpler formula that also displays symmetry between the variables is as follows. Given positive integers a , b , k {\displaystyle a,b,k} , with gcd ( a , b ) = 1 , {\displaystyle \gcd(a,b)=1,} let A k ( a , b ) = { a k , a k − 1 b , … , b k } {\displaystyle A_{k}(a,b)=\{a^{k},a^{k-1}b,\ldots ,b^{k}\}} . Then <a class="footnote-ref" id="fnref:18" href="#fn:18"><sup>18</sup></a> g ( A k ( a , b ) ) = σ k + 1 ( a , b ) − σ k ( a , b ) − ( a k + 1 + b k + 1 ) , {\displaystyle g(A_{k}(a,b))={\sigma }_{k+1}(a,b)-{\sigma }_{k}(a,b)-(a^{k+1}+b^{k+1}),} where σ k ( a , b ) {\displaystyle {\sigma }_{k}(a,b)} denotes the sum of all integers in A k ( a , b ) . {\displaystyle A_{k}(a,b).} <h2 id="examples-and-applications">Examples and applications</h2> <h3>McNugget numbers</h3> <p>One special case of the coin problem is sometimes also referred to as the McNugget numbers. The McNuggets version of the coin problem was introduced by Henri Picciotto, who placed it as a puzzle in Games Magazine in 1987,<a class="footnote-ref" id="fnref:19" href="#fn:19"><sup>19</sup></a> and included it in his algebra textbook co-authored with Anita Wah.<a class="footnote-ref" id="fnref:20" href="#fn:20"><sup>20</sup></a> Picciotto thought of the application in the 1980s while dining with his son at McDonald's, working out the problem on a napkin. A McNugget number is the total number of <a href="/facts/McDonald%27s/Assda4qC">McDonald's</a> <a href="/facts/Chicken_McNuggets/5DxeUxQw">Chicken McNuggets</a> in any number of boxes. In the <a href="/facts/United_Kingdom/kuPAILt2">United Kingdom</a>, the original boxes (prior to the introduction of the <a href="/facts/Happy_Meal/k1FWK1GW">Happy Meal</a>–sized nugget boxes) were of 6, 9, and 20 nuggets. </p><p>According to <a href="/facts/Schur%27s_theorem/2aJCkG2F">Schur's theorem</a>, since 6, 9, and 20 are (setwise) <a href="/facts/Coprime_integers/bnCxCXxs">relatively prime</a>, any sufficiently large integer can be expressed as a (non-negative, integer) <a href="/facts/Linear_combination/CVjL6kuN">linear combination</a> of these three. Therefore, there exists a largest non–McNugget number, and all integers larger than it are McNugget numbers. Namely, every positive integer is a McNugget number, with the finite number of exceptions: </p> 1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28, 31, 34, 37, and 43 (sequence A065003 in the <a href="/facts/On-Line_Encyclopedia_of_Integer_Sequences/yow6cVsU">OEIS</a>). <table><tbody><tr><th>Total</th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th></tr><tr><th>+0</th><td> 0:0,0,0</td><td> 1: —</td><td> 2: —</td><td> 3: —</td><td> 4: —</td><td> 5: —</td></tr><tr><th>+6</th><td> 6:1,0,0</td><td> 7: —</td><td> 8: —</td><td> 9:0,1,0</td><td>10: —</td><td>11: —</td></tr><tr><th>+12</th><td>12:2,0,0</td><td>13: —</td><td>14: —</td><td>15:1,1,0</td><td>16: —</td><td>17: —</td></tr><tr><th>+18</th><td>18:3,0,0</td><td>19: —</td><td>20:0,0,1</td><td>21:2,1,0</td><td>22: —</td><td>23: —</td></tr><tr><th>+24</th><td>24:4,0,0</td><td>25: —</td><td>26:1,0,1</td><td>27:3,1,0</td><td>28: —</td><td>29:0,1,1</td></tr><tr><th>+30</th><td>30:5,0,0</td><td>31: —</td><td>32:2,0,1</td><td>33:4,1,0</td><td>34: —</td><td>35:1,1,1</td></tr><tr><th>+36</th><td>36:6,0,0</td><td>37: —</td><td>38:3,0,1</td><td>39:5,1,0</td><td>40:0,0,2</td><td>41:2,1,1</td></tr><tr><th>+42</th><td>42:7,0,0</td><td>43: —</td><td>44:4,0,1</td><td>45:6,1,0</td><td>46:1,0,2</td><td>47:3,1,1</td></tr><tr><th>+48</th><td>48:8,0,0</td><td>49:0,1,2</td><td>50:5,0,1</td><td>51:7,1,0</td><td>52:2,0,2</td><td>53:4,1,1</td></tr><tr><th>+54</th><td>54:9,0,0</td><td>55:1,1,2</td><td>56:6,0,1</td><td>57:8,1,0</td><td>58:3,0,2</td><td>59:5,1,1</td></tr><tr><td colspan="7">A possible set of combinations of boxes for a total of 0 to 59 nuggets.Each triplet denotes the number of boxes of 6, 9 and 20, respectively.</td></tr></tbody></table> <p>Thus the largest non–McNugget number is 43.<a class="footnote-ref" id="fnref:21" href="#fn:21"><sup>21</sup></a> The fact that any integer larger than 43 is a McNugget number can be seen by considering the following <a href="/facts/Integer_partition/LtyXWqwH">integer partitions</a> </p> 44 = 6 + 6 + 6 + 6 + 20 {\displaystyle 44=6+6+6+6+20} 45 = 9 + 9 + 9 + 9 + 9 {\displaystyle 45=9+9+9+9+9} 46 = 6 + 20 + 20 {\displaystyle 46=6+20+20} 47 = 9 + 9 + 9 + 20 {\displaystyle 47=9+9+9+20} 48 = 6 + 6 + 9 + 9 + 9 + 9 {\displaystyle 48=6+6+9+9+9+9} 49 = 9 + 20 + 20 {\displaystyle 49=9+20+20} <p>Any larger integer can be obtained by adding some number of 6s to the appropriate partition above. A straightforward check demonstrates that 43 McNuggets can indeed <i>not</i> be purchased, as: </p> <ol><li>boxes of 6 and 9 alone cannot form 43 as these can only create multiples of 3 (with the exception of 3 itself);</li> <li>including a single box of 20 does not help, as the required remainder (23) is also not a multiple of 3; and</li> <li>more than one box of 20, complemented with boxes of size 6 or larger, obviously cannot lead to a total of 43 McNuggets.</li></ol> <p>Since the introduction of the 4-piece Happy Meal–sized nugget boxes, the largest non–McNugget number is 11. In countries where the 9-piece size is replaced with the 10-piece size, there is no largest non–McNugget number, as any odd number cannot be made. </p> <h3>Other examples</h3> <p>In <a href="/facts/Rugby_union/AJSbnB89">rugby union</a>, there are four types of scores: penalty goal (3 points), drop goal (3 points), try (5 points) and converted try (7 points). By combining these, any points total is possible except 1, 2, or 4. In <a href="/facts/Rugby_sevens/3LPjqA4X">rugby sevens</a>, although all four types of scoring are permitted, attempts at penalty goals are rare, and drop goals are almost unknown. This means that team scores almost always consist of multiples of tries(5 points) and converted tries (7 points). The following scores (in addition to 1, 2, and 4) cannot be made from multiples of 5 and 7 and so are almost never seen in sevens: 3, 6, 8, 9, 11, 13, 16, 18 and 23. By way of example, none of these scores was recorded in any game in the <a href="/facts/2014-15_Sevens_World_Series/SoXDwMWM">2014-15 Sevens World Series</a>. </p><p>Similarly, in <a href="/facts/American_football/TGzJa1nW">American football</a>, the only way for a team to score exactly one point is if a <a href="/facts/Safety_(American_football_score)/2qR7xQja">safety</a> is awarded against the opposing team when they attempt to <a href="/facts/Conversion_(gridiron_football)/LBW5NuAu">convert</a> after a touchdown (which in this case has a value of 6). As 2 points are awarded for safeties from regular play, and 3 points are awarded for <a href="/facts/Field_goal_(football)/hru6m0aj">field goals</a>, all scores other than 1–0, 1–1, 2–1, 3–1, 4–1, 5–1 and 7–1 are possible. </p> <h3>Shellsort time complexity</h3> <p>The <a href="/facts/Shellsort/DH8sVBfj">Shellsort</a> algorithm is a sorting algorithm whose time complexity is currently an <a href="/facts/Open_problem/VuR6yLsW">open problem</a>. The worst case complexity has an upper bound which can be given in terms of the Frobenius number of a given sequence of positive integers. </p> <h3>Least live weight problem</h3> <p><a href="/facts/Petri_nets/BK7eTHNm">Petri nets</a> are useful for modeling problems in <a href="/facts/Distributed_computing/o5nyhqTF">distributed computing</a>. For specific kinds of Petri nets, namely conservative weighted circuits, one would like to know what possible "states" or "markings" with a given weight are "live". The problem of determining the least live weight is equivalent to the Frobenius problem. </p> <h3>Terms in expanded power of a polynomial</h3> <p>When a univariate polynomial is raised to some power, one may treat the exponents of the polynomial as a set of integers. The expanded polynomial will contain powers of x {\displaystyle x} greater than the Frobenius number for some exponent (when GCD=1), e.g., for ( 1 + x 6 + x 7 ) n {\displaystyle (1+x^{6}+x^{7})^{n}} the set is <i>{6, 7}</i> which has a Frobenius number of 29, so a term with x 29 {\displaystyle x^{29}} will never appear for any value of n {\displaystyle n} but some value of n {\displaystyle n} will give terms having any power of x {\displaystyle x} greater than 29. When the GCD of the exponents is not 1, then powers larger than some value will only appear if they are a multiple of the GCD, e.g. for ( 1 + x 9 + x 15 ) n {\displaystyle (1+x^{9}+x^{15})^{n}} , powers of 24, 27,... will appear for some value(s) of n {\displaystyle n} but never values larger than 24 that are not multiples of 3 (nor the smaller values, 1-8, 10-14, 16, 17, 19-23). </p> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Postage_stamp_problem/EkLEG8r3">Postage stamp problem</a></li> <li><a href="/facts/Change-making_problem/BaU0XNHl">Change-making problem</a></li> <li><a href="/facts/Sylver_coinage/tLKAXmwm">Sylver coinage</a></li> <li><a href="/facts/Numerical_semigroup/5LrBPgmX">Numerical semigroup</a></li></ul> <h2 id="notes">Notes</h2> <h2 id="further-reading">Further reading</h2> <ul><li>Tuenter, Hans J. H. (April 2006). <a href="https://doi.org/10.1016%2Fj.jnt.2005.06.015">"The Frobenius problem, sums of powers of integers, and recurrences for the Bernoulli numbers"</a>. <i>Journal of Number Theory</i>. 117 (2): 376–386. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2Fj.jnt.2005.06.015">10.1016/j.jnt.2005.06.015</a>. <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=2213771">2213771</a>. <a href="/facts/Zbl_(identifier)/P6rFxKKx">Zbl</a> <a href="https://zbmath.org/?format=complete&q=an:1097.11010">1097.11010</a>.</li></ul> <h2 id="external-links">External links</h2> <ul><li><a href="https://www.youtube.com/watch?v=vNTSugyS038">How to order 43 Chicken McNuggets – Numberphile</a></li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>J. Ramírez Alfonsín (2005). The Diophantine Frobenius problem. Oxford Univ. Press. <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Ravi Kannan (1992). "Lattice translates of a polytope and the Frobenius problem". Combinatorica. 12 (2): 161–177. doi:10.1007/BF01204720. S2CID 19200821. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>D. Beihoffer; J. Hendry; A. Nijenhuis; S. Wagon (2005). "Faster algorithms for Frobenius numbers". Electronic Journal of Combinatorics. 12: R27. doi:10.37236/1924. <a href="http://www.combinatorics.org/Volume_12/Abstracts/v12i1r27.html" target="_blank">http://www.combinatorics.org/Volume_12/Abstracts/v12i1r27.html</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Weisstein, Eric W. "Coin Problem". MathWorld. <a href="/wiki/Eric_W._Weisstein" target="_blank">/wiki/Eric_W._Weisstein</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>Weisstein, Eric W. "Coin Problem". MathWorld. <a href="/wiki/Eric_W._Weisstein" target="_blank">/wiki/Eric_W._Weisstein</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>Sylvester, James Joseph (1882). "On subinvariants, i.e. Semi-Invariants to Binary Quantics of an Unlimited Order". American Journal of Mathematics. 5 (1): 134. doi:10.2307/2369536. JSTOR 2369536. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>The original source is sometimes incorrectly cited as,[6] in which the author put his theorem as a recreational problem[7] (and did not explicitly state the formula for the Frobenius number). <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>Skupień, Zdzisław (1993). "A generalization of Sylvester's and Frobenius' problems" (PDF). Acta Arithmetica. LXV.4 (4): 353–366. doi:10.4064/aa-65-4-353-366. <a href="/wiki/Zdzis%C5%82aw_Skupie%C5%84" target="_blank">/wiki/Zdzis%C5%82aw_Skupie%C5%84</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>Tripathi, A. (2017). "Formulae for the Frobenius number in three variables". Journal of Number Theory. 170: 368–389. doi:10.1016/j.jnt.2016.05.027. <a href="https://doi.org/10.1016%2Fj.jnt.2016.05.027" target="_blank">https://doi.org/10.1016%2Fj.jnt.2016.05.027</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> <li id="fn:10"><p>See numerical semigroup for details of one such algorithm. <a href="/wiki/Numerical_semigroup" target="_blank">/wiki/Numerical_semigroup</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li> <li id="fn:11"><p>M. Beck; S. Zacks (2004). "Refined upper bounds for the linear Diophantine problem of Frobenius". Adv. Appl. Math. 32 (3): 454–467. arXiv:math/0305420. doi:10.1016/S0196-8858(03)00055-1. S2CID 119174157. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li> <li id="fn:12"><p>Ustinov, A. (2009). "The solution of Arnold's problem on the weak asymptotics of Frobenius numbers with three arguments". Sbornik: Mathematics. 200 (4): 131–160. Bibcode:2009SbMat.200..597U. doi:10.1070/SM2009v200n04ABEH004011. <a href="/wiki/Bibcode_(identifier)" target="_blank">/wiki/Bibcode_(identifier)</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></p></li> <li id="fn:13"><p>Wilf, H.S. (1978). "A Circle-Of-Lights Algorithm for the "Money-Changing Problem"". The American Mathematical Monthly. 85 (7): 562–565. doi:10.2307/2320864. JSTOR 2320864. <a href="https://www.jstor.org/stable/2320864" target="_blank">https://www.jstor.org/stable/2320864</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></p></li> <li id="fn:14"><p>Moscariello, A.; Sammartano, A. (2015). "On a Conjecture by Wilf About the Frobenius Number". Mathematische Zeitschrift. 280 (1–2): 47–53. arXiv:1408.5331. doi:10.1007/s00209-015-1412-0. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></p></li> <li id="fn:15"><p>Ramirez Alfonsin, Jorge (2005). The Diophantine Frobenius Problem. Oxford University Press. pp. 59–60. <a href="#fnref:15" class="footnote-back-ref">↩</a></p></li> <li id="fn:16"><p>Lee, S.H.; O'neill, C.; Van Over, B. (2019). "On arithmetical numerical monoids with some generators omitted". Semigroup Forum. 98 (2): 315–326. arXiv:1712.06741. doi:10.1007/s00233-018-9952-3. S2CID 119143449. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></p></li> <li id="fn:17"><p>Ong, Darren C.; Ponomarenko, Vadim (2008). "The Frobenius Number of Geometric Sequences". INTEGERS: The Electronic Journal of Combinatorial Number Theory. 8 (1): A33. Retrieved 2010-01-04. <a href="http://www.emis.de/journals/INTEGERS/papers/i33/i33.Abstract.html" target="_blank">http://www.emis.de/journals/INTEGERS/papers/i33/i33.Abstract.html</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></p></li> <li id="fn:18"><p>Tripathi, Amitabha (2008). "On the Frobenius Problem for Geometric Sequences, Article A43". INTEGERS: The Electronic Journal of Combinatorial Number Theory. 8 (1). <a href="#fnref:18" class="footnote-back-ref">↩</a></p></li> <li id="fn:19"><p>Picciotto, Henri (1987). "Math McPuzzle". Games Magazine. 85 (April/May): 52. <a href="https://archive.org/details/games-85-1987-april/page/n53/mode/2up" target="_blank">https://archive.org/details/games-85-1987-april/page/n53/mode/2up</a> <a href="#fnref:19" class="footnote-back-ref">↩</a></p></li> <li id="fn:20"><p>Wah, Anita; Picciotto, Henri (1994). "Lesson 5.8 Building-block Numbers" (PDF). Algebra: Themes, Tools, Concepts. p. 186. <a href="http://www.mathedpage.org/attc/lessons/ch.05/5.08-building-blocks.pdf" target="_blank">http://www.mathedpage.org/attc/lessons/ch.05/5.08-building-blocks.pdf</a> <a href="#fnref:20" class="footnote-back-ref">↩</a></p></li> <li id="fn:21"><p>Weisstein, Eric W. "McNugget Number". MathWorld. <a href="/wiki/Eric_W._Weisstein" target="_blank">/wiki/Eric_W._Weisstein</a> <a href="#fnref:21" class="footnote-back-ref">↩</a></p></li> </ol>