## McNugget Numbers

### December 9, 2011

Since 6, 9, and 20 are coprime and their least common multiple is 180, we know that any number larger than 180 is a McNugget number. To find the list of numbers less than 180 that are McNugget numbers we calculate as follows:

```(define non-mcnuggets   (sort <     (list-minus       (range 181)       (unique =         (list-of m           (x range (+ (/ 180 6) 1))           (y range (+ (/ 180 9) 1))           (z range (+ (/ 180 20) 1))           (m is (+ (* 6 x) (* 9 y) (* 20 z)))           (<= m 180))))))```

The list comprehension computes m=6x+9y+20z for all combinations of x, y and z that could be less than 180, then `list-minus` figures those numbers that are not on the list. Here is `list-minus`:

```(define (list-minus xs ys)   (let loop ((xs xs) (zs (list)))     (cond ((null? xs) zs)           ((member (car xs) ys) (loop (cdr xs) zs))           (else (loop (cdr xs) (cons (car xs) zs))))))```

The list of non-McNugget numbers is 1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28, 31, 34, 37, and 43. If you’re interested in the math, the Frobenius number of the set {6 9 20} is 43, which is the largest non-McNugget number; Google will point you to more.

We used list comprehensions, unique and range from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/01h2PiHK.

Pages: 1 2

### 14 Responses to “McNugget Numbers”

1. […] today’s Programming Praxis exercise, our goal is to determine all the numbers that are not McNugget […]

```import Data.List

notMcNuggets :: [Integer]
notMcNuggets = [1..180] \\
[a+b+c | a <- [0,6..180], b <- [0,9..180-a], c <- [0,20..180-a-b]]
```
3. […] response to this challenge McNugget numbers  I wrote C code based on a different approach than exhibited in the LISP solution and obviously […]

4. […] I heard from my friend about the new programming praxis problem I started thinking how to implement the solution. I wrote down the numbers from 1 to 20 and […]

5. Python solution along the same lines as the C one, but self-documenting,

My thinking is described here: http://ctopy.wordpress.com/2011/12/09/mcnugget-numbers-python-solution/

```
known = [ 0 ]
i = 1
consecutive_success = 0

while True:
if i - 6 in known or i - 9 in known or i - 20 in known:
known.append(i)
consecutive_success += 1
if consecutive_success == 6:
print "All numbers >=  %d are mcnugget" % (i - 5)
break
else:
print i
consecutive_success = 0
i += 1

```
6. nee said

I’ve tried to make a Haskell solution using somewhat less mathematical knowlegde (for example the one that we only have to check the numbers smaller than 180).

```import Data.List
mc = mchelp   
where mchelp s@(a:_) n@(b:_) t@(c:_) =  min:mchelp (p s 6) (p n 9) (p t 20)
where min = minimum [a+6,b+9,c+20]
p (x:l) n = (if x+n==min then id else (x:)) l++[min]

notmc = [1..last \$ needed mc] \\ (needed mc)
where needed (x:l) = x:(if l!!4 == x+5 then [] else needed l)
```

The ugly function mc calculates the infinite list of McNugget numbers in increasing order. For example the first 50:

```*Main> take 50 \$ mc
[6,9,12,15,18,20,21,24,26,27,29,30,32,33,35,36,38,39,40,41,42,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72]
```

And notmc gives the solution /it stops if 6 consecutive McNugget numbers are found, because each larger number can be generated easily by adding 6 to them repeatedly/:

```*Main> notmc
[1,2,3,4,5,7,8,10,11,13,14,16,17,19,22,23,25,28,31,34,37,43]
```
7. nee said

And a haskell copy of the popular solution of Tomasz Kwiatkowskis:
[/sourcecode]
notmc = helper  [1..]
where helper _ [] = []
helper is (x:xs)
| length is > 5 && head is – 5 == is!!5 = []
| otherwise = if any (\a-> elem a is) [x-6,x-9,x-20]
then helper (x:is) xs
else x:helper is xs
[/sourcecode]

8. Graham said

Probably not the most efficient solution, but in relatively short Python:

```from itertools import ifilter, imap, product
print set(xrange(181)) - set(ifilter(lambda s: s < 181,
imap(sum, product(xrange(0, 181, 6),
xrange(0, 181, 9),
xrange(0, 181, 20)))))
```

The use of the procedures from the `itertools` module ensures no intermediate lists are constructed.

9. Ashish said

I still don’t get why 181 or 182 is not a mcnugget number. You it can not summed using 6,9,20

10. programmingpraxis said

22*6 + 1*9 + 2*20 = 181

24*6 + 2*9 + 1*20 = 182

11. Nelson said

Java approach:

```public class McNuggetNumber {

public static boolean check(int num) {
int minusSix = num - 6;
int minusNine = num - 9;
int minusTwenty = num - 20;
if (minusSix == 0) {
return true; // 6
} else if (minusNine == 0) {
return true; // 9
} else if (minusTwenty == 0) {
return true;
} else if (minusSix < 0) {
return false;
}
return check(minusSix) || check(minusNine) || check(minusTwenty);
}

public static void main(String[] args) {
for (int index = 1; index < 180; index++) {
if (!check(index)) {
System.out.println(index);
}
}
}
}

```
12. Nosayba said

Please I have a question … How it is determined that all numbers after LCM “180” are MCNuggets number?