Chicken McNugget Numbers

Question

Description

Chicken McNugget numbers are numbers that can be expressed as a sum of \6ドル\$, \9ドル\$ or \20ドル\$ - the initial sizes of the famous Chicken McNuggets boxes sold by McDonald's. In that sum, a number may occur more than once, so \6ドル + 6 = 12\$ is such a number too, and the number must "contain" at least one of the mentioned sizes. The first Chicken McNugget numbers are:

\begin{align*}&6\\ &9\\ &6 + 6 = 12\\ &6 + 9 = 15\\ &9 +たす 9 =わ 6 +たす 6 +たす 6 =わ 18\\ &20\\ &6 + 6 + 9 = 21\\ &\dots \end{align*}

Challenge

Your task is to write a program or function, that, given a positive integer, determines whether this number can be expressed in the described way, therefore is such a Chicken McNugget number. It should then output a truthy or falsy value based on its decision.

Test cases

6 -> true
7 -> false
12 -> true
15 -> true
21 -> true
40 -> true
42 -> true

This is code-golf, so the shortest answer in bytes wins and the standard loopholes apply!

• Leaky Nun: It should be noted that "All integers are McNugget numbers except 1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28, 31, 34, 37, and 43." (mathworld)
• racer290: Well, then let's take it as a compression challenge, but thanks for the note
• CraigR8806: Anybody have an OEIS link for this???
• Dan Is Fiddling By Firelight: What do you have against the 4 piece nugget pack? mcdonalds.com/us/en-us/product/chicken-mcnuggets-4-piece.html
• Jason C: numberphile...

Answer 1

Python, 27 bytes

lambda n:0x82492cb6dbf>>n&1

Try it online!

• hyperneutrino: What is this magical code o_O this is amazing
• Leaky Nun: You can remove the ~ because you can swap the outputs.
• Leaky Nun: Also, 8953174650303 has the exact same length with 0x82492cb6dbf (albeit less readable).
• David Z: @HyperNeutrino the magic number has only those bits set which correspond to numbers that are not Chicken McNugget numbers. Look at its binary representation and it'll be much clearer.
• Jacob Garby: Shame you can't easily use this same idea with base 64

Answer 2

Python 3, 24 bytes

lambda n:0<=n--n%3*20!=3

Try it online!

Explanation

With 6 and 9 alone, one can make all integers divisible by 3 which are greater than 3, as is stated in ovs's comment to the challenge. It is assumed that one can also make 0. In conclusion, one can make 0,6,9,12,15,....

With one instance of 20, one can make: 20,26,29,32,35,....

With two instances of 20, one can make: 40,46,49,52,55,....

Three instances is never necessary, for 3 x 20 = 10 x 6.

---

Notice that the cases where no 20 is needed is also divisible by 3; the cases where one 20 is needed leaves a remainder of 2; the cases where two 20 is needed leaves a remainder of 1.

The number of 20 needed can hence be calculated by (-n)%3. Then, we do n-(((-n)%3)*20) to remove the number of 20 needed from the number. We then check that this number is non-negative, but is not 3.

• Mr. Xcoder: 39 bytes
• Leaky Nun: @Mr.Xcoder updated.
• Adalynn: f=lambda n:n%3<1<n-2or n>20and f(n-20) does that work?
• notjagan: 37 bytes.
• notjagan: You can remove the f= now since it's not recursive.

Answer 3

Python 2, 28 bytes

lambda n:-n%3-n/20<(n%20!=3)

Try it online!

• Leaky Nun: Using some trial-and-error and mapping the first part to the range, I have a rough idea of how it works. However, I would like to know how you came up with this solution.
• xnor: @LeakyNun Funny, I thought this was the natural method and yours was the clever one :). I noted the possible values of (n%3,n/20) from your excluded list are {(2, 0), (1, 0), (1, 1)}. Using -n%3 instead gave an inequality n/20>=(-n)%3. From there, I fiddled a while to reverse {3,23,43} which are 3 mod 20 without affecting 63,83,... I found shifting the inequality endpoint for these worked nicest.
• Leaky Nun: Well my method involves really solving the problem whereas your method is fiddling with the values in the excluded list, so I'd say that my method is more natural :)

Answer 4

Jelly, 11 bytes

ṗ3’æ."©μÞ‘ċ

Try it online!

How it works

ṗ3’æ."©μÞ‘ċ Main link. Argument: n
ṗ3 Cartesian power; yield all 3-tuples over [1, ..., n].
 ’ Decrement all coordinates.
 "©μÞ‘ Yield [6, 9, 20].
 æ. Take the dot product of each 3-tuple and [6, 9, 20].
 ċ Count the occurrences of n (Positive for Chicken McNuggets numbers).

• CJ Dennis: Chicken McNuggetsTM and Jelly! Mmmm!!!
• caird coinheringaahing: @CJDennis Actually it's Chicken McNuggets© and Jelly.
• Dan: @cairdcoinheringaahing Actually it's Chicken McNuggets® and Jelly.

Answer 5

Haskell, 36 bytes

f n|n<1=n==0
f n=any(f.(n-))[6,9,20]

Try it online!

Explanation

This solution is about as straightforward as it can get. The first line declares that for any number less than 1 it is a McNugget number if n==0. That is to say that 0 is a McNugget number and all negative numbers are not.

The second line declares that for all other numbers, n is a McNugget number if it minus any of the Nugget sizes is a McNugget number.

This is a pretty simple recursive search.

Answer 6

Python 3, (削除) 48 (削除ここまで) (削除) 46 (削除ここまで) 42 bytes

lambda n:n+50in b'2345679:<=?@BCEHIKNQTW]'

Try it online!

Switches True and False.

• Mr. Xcoder: You can switch True and False by default

Answer 7

Jelly, 11 bytes

_20$%3$¿o>3

Try it online!

Port of my Python answer, but slightly modified: subtract 20 until divisible by 3, then check whether it belongs to 0,6,9,... by mapping 0 to the input (by using or), and then check if it is greater than 3.

The only three numbers that produce 0 upon completing the first step is 0, 20, or 40, with the first one being out of the domain, and the rest being greater than 3.

• racer290: I dont get how to enter the input..
• Erik the Outgolfer: @racer290 Command-line argument.

Answer 8

Mathematica, 53 bytes

!Flatten@Table[Tr/@Tuples[{6,9,20},i],{i,#}]~FreeQ~#&

• alephalpha: Maybe you can use the FrobeniusSolve function.

Answer 9

Mathematica, 30 bytes

{6,9,20}~FrobeniusSolve~#!={}&

Try it on Wolfram Sandbox.

Answer 10

Mathematica, 20 bytes

0<=#-20Mod[-#,3]!=3&

Anonymous function. Takes a number as input and returns True or False as output. Logic copied from Leaky Nun's answer, with some added abuse of Inequality.

Answer 11

x86-64 Machine Code, 22 bytes

48 B8 41 92 34 6D DB F7 FF FF 83 F9 40 7D 03 48 D3 E8 83 E0 01 C3

The above bytes define a function in 64-bit x86 machine code that determines whether the input value is a Chicken McNugget number. The single positive integer parameter is passed in the ECX register, following the Microsoft 64-bit calling convention used on Windows. The result is a Boolean value returned in the EAX register.

Ungolfed assembly mnemonics:

; bool IsMcNuggetNumber(int n)
; n is passed in ECX
 movabs rax, 0xFFFFF7DB6D349241 ; load a 64-bit constant (the bit field)
 cmp ecx, 64
 jge TheEnd ; if input value >= 64, branch to end
 shr rax, cl
TheEnd:
 and eax, 1 ; mask off all but LSB
 ret

Obviously, this plays heavily off of Anders Kaseorg's solution in Python, in that it is based around a bit-field representing the values that are Chicken McNugget numbers. Specifically, each bit in this field that corresponds to a valid Chicken McNugget number is set to 1; all other bits are set to 0. (This considers 0 to be a valid Chicken McNugget number, but if you don't like that, your preference is a single-bit modification away.)

We start off by simply loading this value into a register. It is a 64-bit value, which already takes 8 bytes to encode, plus we need a one-byte REX.W prefix, so we are really being quite spendthrift in terms of bytes, but this is the heart of the solution, so I guess it's worth it.

We then shift the field right by the input value.^* Finally, we mask off all but the lowest-order bit, and that becomes our Boolean result.

However, since you cannot shift by more than the number of bits actually in the value, this works only for inputs from 0–63. To support higher input values, we insert a test at the top of the function that branches to the bottom of the input value is >= 64. The only thing interesting about this is the we preload the bit-field constant in RAX, and then branch down to the instruction that masks off the lowest-order bit, thus ensuring that we always return 1.

Try it online!
_{(The C function call there is annotated with an attribute that causes GCC to call it using the Microsoft calling convention that my assembly code uses. If TIO had provided MSVC, this wouldn't be necessary.)}

__
_{* As an alternative to a shift, we could have used the x86 BT instruction, but that's 1 byte longer to encode, so no advantage. Unless we were forced to use a different calling convention that didn't conveniently pass the input value in the ECX register. This would be a problem because SHR requires that its source operand be CL for a dynamic shift count. Therefore, a different calling convention would require that we MOVed the input value from whatever register it was passed in to ECX, which would cost us 2 bytes. The BT instruction can use any register as a source operand, at a cost of only 1 byte. So, in that situation, it would be preferable. BT puts the value of the corresponding bit into the carry flag (CF), so you would use a SETC instruction to get that value in an integer register like AL so it could be returned to the caller.}

---

Alternative implementation, 23 bytes

Here is an alternative implementation that uses modulo and multiplication operations to determine whether the input value is a Chicken McNugget number.

It uses the System V AMD64 calling convention, which passes the input value in the EDI register. The result is still a Boolean, returned in EAX.

Note, though, that unlike the above code, this is an inverse Boolean (for implementation convenience). It returns false if the input value is a Chicken McNugget number, or true if the input value is not a Chicken McNugget number.

 ; bool IsNotMcNuggetNumber(int n)
 ; n is passed in EDI
8D 04 3F lea eax, [rdi+rdi*1] ; multiply input by 2, and put result in EAX
83 FF 2B cmp edi, 43
7D 0E jge TheEnd ; everything >= 43 is a McNugget number
99 cdq ; zero EDX in only 1 byte
6A 03 push 3
59 pop rcx ; short way to put 3 in ECX for DIV
F7 F1 div ecx ; divide input value by 3
6B D2 14 imul edx, edx, 20 ; multiply remainder of division by 20
39 D7 cmp edi, edx
0F 9C C0 setl al ; AL = (original input) < (input % 3 * 20)
 TheEnd:
C3 ret

What's ugly about this is the need to explicitly handle input values >= 43 by a compare-and-branch at the top. There are obviously other ways of doing this that don't require branching, like caird coinheringaahing's algorithm, but this would take a lot more bytes to encode, so isn't a reasonable solution. I figure I'm probably missing some bit-twiddling trick that would make this work out more elegantly and be fewer bytes than the bitfield-based solution above (since encoding the bitfield itself takes so many bytes), but I've studied this for a while and still can't see it.

Oh well, try it online anyway!

Answer 12

05AB1E, (削除) 17 (削除ここまで) 16 bytes

ŽGç2в©IED®âO«]I¢

Try it online!

Explanation

 ŽGç2в The list [6, 9, 20]
 © Store this list in register_c
 IE Loop <input> number of times
 ®â Cartesian product stack contents with list in register_c
 O Sum up the contents of each sub array
 D « List duplicated before taking Cartesian product, concat
 ] End for loop
 I¢ Count occurences of input

• Gymhgy: You have duplicate TIO links.
• Kevin Cruijssen: Nice answer. Welcome to PPCG and the world of 05AB1E. :) One thing to golf is to use ... for the string (there are buitins for 1-, 2-, and 3-char strings, being ', „, and ... respectively). I have the feeling more can be golfed, perhaps by using a different approach, but regardless this is a nice first answer. +1 from me.
• Kevin Cruijssen: Was indeed correct. Found a 12-byter by utilizing the builtin Åœ: ... ÇIÅœåPOĀ. It's a completely different approach, so if you want me to post it as a separated answer rather than a golf of yours, let me know. PS: I'm not 100% sure if the unprintables are allowed in the 05AB1E codepage. It might have to be in a different encoding in that case, which would make some characters count as 2 bytes each instead.. In that case ŽBo21в could be an alternative for +1 byte.
• Emigna: Like Kevin mentions, neither of the 3 bytes in your string are in the 05ab1e code page and thus can't be used without counting the whole program in utf-8 which would make it a lot longer. You can however use ŽGç2в instead of the string while simultaneously saving a byte in the process.
• rev: Kevin, go for it. It'd be nice to see different approaches. Emigna, thanks for you suggestion, I will make the change

Answer 13

JavaScript (ES6), (削除) 69 (削除ここまで) 64 bytes

n=>'ABCDEFHIKLNOQRTWXZ]`cfl'.includes(String.fromCharCode(n+65))

f=
n=>'ABCDEFHIKLNOQRTWXZ]`cfl'.includes(String.fromCharCode(n+65))

<input onkeydown=a.innerHTML=f(this.value)>
<pre id=a>

Outputs false for Chicken McNugget numbers, true otherwise.

• racer290: I'd like at least a "try it" link..
• darrylyeo: @racer290 Added.
• Oki: n=>~'ABCDEFHIKLNOQRTWXZ]`cfl'.search(String.fromCharCode(n+65)) for 63 bytes

Answer 14

Java, (削除) 21 (削除ここまで) (削除) 57 (削除ここまで) 24 bytes

Try it online!

Golfed:

n->(n-=n*2%3*20)>=0&n!=3

Ungolfed:

import java.util.*;
public class ChickenMcNuggetNumbers {
 private static final Set<Integer> FALSE_VALUES = new HashSet<>(Arrays.asList(
 new Integer[] { 0, 1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23,
 25, 28, 31, 34, 37, 43 }));
 public static void main(String[] args) {
 for (int i = 0; i < 45; ++i) {
 System.out.println(i + " -> expected=" + !FALSE_VALUES.contains(i)
 + ", actual=" + f(n->(n-=n*2%3*20)>=0&n!=3, i));
 }
 }
 public static boolean f(java.util.function.Function<Integer, Boolean> f, int n) {
 return f.apply(n);
 }
}

• Leaky Nun: Result is wrong for 26 = 20 + 6.
• user18932: @LeakyNun Algorithm was too naive. I had to go with plan B which added some bytes, but appears to produce correct results all of the time now. I should have iterated all of the values to begin with instead of relying on the test cases in the question.
• Leaky Nun: 35 bytes
• Leaky Nun: 24 bytes (see above)
• user18932: @LeakyNun thanks! I still have a lot to learn about golfing.

Answer 15

Add++, 35 bytes

D,f,@,A6$%0=@20$%0=A3$%0=A8<A43<s1<

Try it online!

Look ma, no while loops. Or strings. Or lists. Or really anything that helps save bytes. But mainly because Add++ doesn't know what any of those are.

3 months later, I realised that this was invalid, and fixed it. Somehow, that golfed it by 13 bytes. This is a function that takes one argument and tests whether that argument is a Chicken McNugget number or not.

How it works

D,f,@, - Create a monadic (one argument) function called f (example argument: 3)
A - Push the argument again; STACK = [3 3]
 6 - Push 6; STACK = [3 3 6]
 $ - Swap the top two values; STACK = [3 6 3]
 % - Modulo; STACK = [3 3]
 0 - Push 0; STACK = [3 3 0]
 = - Are they equal? STACK = [3 0]
 @ - Reverse the stack; STACK = [0 3]
 20 - Push 20; STACK = [0 3 20]
 $ - Swap the top two values; STACK = [0 20 3]
 % - Modulo; STACK = [0 3]
 0 - Push 0; STACK = [0 3 0]
 = - Are they equal? STACK = [0 0]
 A - Push the argument; STACK = [0 0 3]
 3 - Push 3; STACK = [0 0 3 3]
 $ - Swap the top two values; STACK = [0 0 3 3]
 % - Modulo; STACK = [0 0 0]
 0 - Push 0; STACK = [0 0 0 0]
 = - Are they equal? STACK = [0 0 1]
 A - Push the argument; STACK = [0 0 1 3]
 8 - Push 8; STACK = [0 0 1 3 8]
 < - Less than; STACK = [0 0 1 0]
 A - Push the argument; STACK = [0 0 1 0 3]
 43 - Push 43; STACK = [0 0 1 0 3 43]
 < - Less than; STACK = [0 0 1 0 0]
 s - Sum; STACK = [1]
 1 - Push 1; STACK = [1 1]
 < - Less than; STACK = [0]

Answer 16

Python 2, 51 bytes

-1 byte thanks to @LeakyNun

lambda n:max(n>43,25<n>n%3>1,5<n>n%3<1,n in[20,40])

Try it online! Footer prints all non McNugget numbers

• Leaky Nun: n%3 can only be 0 or 1 or 2, so n%3==2 is equivalent to n%3>1.

Answer 17

Pyth, 15 bytes

fg.{CM" "{T./

Try it online!

The string contains the characters corresponding to codepoints 6, 9, and 20.

Answer 18

Haskell, (削除) 64 (削除ここまで) 56 bytes

I didn't do any bit trickery, but looking at the other answers it might actually be shorter to import the Bits module and use those methods. This approach checks much more directly.

f x=(\l->elem x[i*6+j*9+k*20|i<-l,j<-l,k<-l,x/=0])[0..x]

• ბიმო: The byte count is 66 not 64. But you you can save a lot of parenthesis and put an x/=0 guard to save some bytes, see here.

Answer 19

Javascript, (削除) 92 (削除ここまで) (削除) 78 (削除ここまで) 72 bytes

*saved 14 bytes thanks to @Jonasw

a=>!(a in[0,1,2,3,4,5,7,8,10,11,13,14,16,17,19,22,23,25,28,31,34,37,43])

Uses the fact that "All integers are McNugget numbers except 1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28, 31, 34, 37, and 43." from @LeakyNun's comment

• Jonas Wilms: using a simple array would save the bytes for .split ...
• SuperStormer: @Jonas array is 108 bytes, splitted string is 73 bytes
• Jonas Wilms: um jsbin.com/bucihuqefi/edit?console -11 bytes...

Answer 20

APL (Dyalog), 19 bytes

⊢∊6 9 ×ばつ⍨∘↑∘⍳3⍴⊢

with ⎕IO←0

Same algorithm with Dennis's answer

Try it online!

Answer 21

Retina, 26 bytes

.+
$*
^(1{6}|1{9}|1{20})+$

Try it online!

Answer 22

Excel, 87 bytes

=AND(OR(MOD(A1,3)*MOD(A1,20)*IF(A1>43,MOD(A1-40,3),1)*IF(A1>23,MOD(A1-20,3),1)=0),A1>5)

Alternatively, 92 bytes:

=CHOOSE(MOD(A1,3)+1,A1>3,IF(A1>43,MOD(A1-40,3)=0,A1=40),IF(A1>23,MOD(ABS(A1-20),3)=0,A1=20))

Answer 23

PHP, 69+1 bytes

for($n=$argn;$n>0;$n-=20)if($n%3<1)for($k=$n;$k>0;$k-=9)$k%6||die(1);

exits with 1 for a Chicken McNugget Number, 0 else.

Run as pipe with -n or try it online.

Answer 24

Jelly, 10 bytes

Œṗḟ€"©μÞ‘Ạ

Try it online!

Outputs in the opposite direction; returning false indicates that the input is a Chicken McNugget number. The TIO footer swaps this for you.

How it works

Œṗḟ€"©μÞ‘Ạ - Main link. Takes an integer n on the left
Œṗ - Integer partitions of n; all ways to sum integers to n
 "©μÞ‘ - Yield [6, 9, 20]
 € - Over each partition P:
 ḟ - Remove all 6s, 9s and 20s
 Ạ - Are all resulting lists non-empty?

Answer 25

Python 2, 61 bytes

lambda n:n in[int(c,36)for c in'1234578ABDEGHJMNPSV']+[37,43]

Try it online!

• Leaky Nun: Or you could use codepoints and decompress with chr.

Answer 26

Mathematica, 59 bytes

!Select[IntegerPartitions@#,{6,9,20}~SubsetQ~#&]=={}&&#!=0&

Answer 27

Javascript 37 bytes

Takes a positive integer n and outputs true for Chicken McNugget numbers and false for others.

F=n=>!(n<0||(n%6&&!F(n-9)&&!F(n-20)))

Explanation

F=n=>!( // negate the internal test for non-Chicken McNugget numbers
 n<0 || ( // if n < 0, or
 n%6 && // if n % 6 is truthy,
 !F(n-9) && // and n-9 is not a Chicken McNugget number
 !F(n-20) // and n-20 is not a Chicken McNugget number
 // then n is not a Chicken McNugget number
 )
)

The recursion on this function is heinous, and for any sufficiently large n, you will exceed call stack limits. Here's a version that avoids those limits by checking if n is larger than the largest non-Chicken McNugget number (43 bytes [bonus points for being the largest non-Chicken McNugget number?]):

F=n=>n>43||!(n<0||(n%6&&!F(n-9)&&!F(n-20)))

F=n=>n>43||!(n<0||(n%6&&!F(n-9)&&!F(n-20)))
$('#input').on('keyup', () => $('#output').text(F(parseInt($('#input').val(), 10))))

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<input type="text" id="input" />
<span id="output"></span>

Answer 28

JavaScript ES5, 46 bytes

n=>n>5&&(!(n%20)||(n<24?!(n%3):n<44?n%3-1:1));

Explicit boolean answer, 50 bytes:

n=>!!(n>5&&(!(n%20)||(n<24?!(n%3):n<44?n%3-1:1)));

Clumsy, but it gets the job done. Returns false or 0 for every value that isn't 0, 1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28, 31, 34, 37, or 43, and true, -1, or 1 for everything else.

Explicit solution returns true or false only.

n=>!!( ); forces Boolean type (optional)
 n>5 false for 0, 1, 2, 3, 4, 5 (and negative inputs)
 !(n%20) explicit true for 20, 40
 n<24?!(n%3) false for 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23
 n<44?n%3-1 false for 25, 28, 31, 34, 37, 43

Answer 29

Clojure 33 bytes

An on ok quick attempt: #(-> %(rem 20)(rem 9)(rem 6)(= 0))

Answer 30

Pari/GP, 44 bytes

n->n&&#(1/(1-x^6)/(1-x^9)/(1-x^20)%x^n++)==n

Try it online!

• ZaMoC: Irrelevant comment : what was the problem with this answer of yours?#~SetPrecision~1& ?
• alephalpha: @Jenny_mathy It fails the 0.25 test case.