Puzzles of the Week

THE CHALLENGE & EXPLORATION

This is trickier than what happens in “Broken Calculator – 1.” The math theorem involved is affectionately called the McNugget Theorem. Suppose you have two relatively prime numbers n and m – that is, their greatest common factor (divisor) is 1. The theorem says that you can produce exactly half of the numbers from 1 to (n – 1) x (m – 1) as sums of positive multiples of n and m, and that starting with (n – 1) x (m – 1) you can produce every number thereafter.

Applying this theorem to 4 and 7, we know that we can produce half the numbers up to (4 – 1) x (7 – 1) = 18, and that from then on we can make all numbers. Let’s see how that works in this special case.

• 1 = Impossible
• 2 = impossible
• 3 = impossible
• 4 = 4
• 5 = impossible
• 6 = impossible
• 7 = 7
• 8 = 4 + 4
• 9 = impossible
• 10 = impossible
• 11 = 4 + 7
• 12 = 4 + 4 + 4
• 13 = impossible
• 14 = 7 + 7
• 15 = 4 + 4 + 7
• 16 = 4 + 4 + 4 + 4
• 17 = impossible
• 18 = 4 + 7 + 7

Without understanding any fancy number theory, the intrepid explorer might notice that half the numbers from 1 to 18 are possible and the other half are impossible. They might also notice the pattern that x is possible exactly when 17 – x is possible.

Another pattern to notice is that any common multiple of the two numbers will divide all of the sums of the multiples of the two numbers. This means that if the two numbers have a common multiple greater than 1, then there will be an infinite number of numbers that cannot be produced by that calculator. For example, combinations of 4 and 6 will never produce an odd number.