Frobenius Numbers – Round Robin Algorithm

September 20, 2010 at 14:50 (algorithm, java, math.NT)

Frobenius numbers are solutions to the coin problem. Let \displaystyle 0<a_1<\cdots<a_n be coin denominations; what is the smallest sum of money that cannot be obtained using these coins? More formally, define the Frobenius number \displaystyle g(a_1,\,\ldots\,,a_n) as the greatest number that is not a linear combination \sum_{i=1}^n x_ia_i with \displaystyle 0 \le x_i \in \mathbb{Z} . The Frobenius number exists if and only if \displaystyle a_1 > 1 and \displaystyle \gcd(a_1,\,\ldots\,,a_n)=1 . A special case of Frobenius numbers involves the interestingly named McNugget numbers, and there is a well-known formula when \displaystyle n=2 given by \displaystyle g(a_1,a_2)=a_1a_2-a_1-a_2 sometimes known as the Chicken McNugget Theorem.

Read the rest of this entry »

Permalink Leave a Comment

Continued Fractions of Square Roots – Steps

July 4, 2010 at 19:31 (algorithm, java, math.NT, tutorial)

Everyone knows what continued fractions are, right? Continued fractions have interesting properties and can be used to obtain best rational approximations for real numbers, among other things. Here is an example of a finite continued fraction:

8.309 = 8+\cfrac{1}{3+\cfrac{1}{4+\cfrac{1}{4+\cfrac{1}{3+\cfrac{1}{2+\cfrac{1}{2}}}}}}

Read the rest of this entry »

Permalink Leave a Comment