McNugget Numbers

McNugget Numbers are any integer n which can be satisfied with the linear combination of 6a + 9b + 20c. Although it is known that all integers (with some exceptions*) are McNugget Numbers, it is still interesting to see how many possible linear combinations can be used to satisfy some n.

Chicken McNuggets x20I’ve designed this small program to test if a number is potentially a McNugget Number. It will quickly sieve through if the number is able to satisfied with a x6 McNugget Box, a x9 McNugget Box or a x20 McNugget Box. Note that the program doesn’t consider all the possible ways of satisfying some integer n.

For example, 36 can be satisfied with {6,0,0}, {0,4,0} and {3,2,0}.

*As said earlier, the exception set of integers is the following: {1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28, 31, 34, 37, 43}, if we use the original box size set of {6, 9, 20}. I’ve ignored the newer {4,6,9,20} set of coefficients for the linear combination since this drastically reduces the number of non McNugget numbers to the set of {1, 2, 3, 5, 7, 11}.

The code is written in C++. The source file can download directly from here.

References:

McNugget Number – from Wolfram MathWorld

 

 

 

 

 

Advertisements

About 0x14c

I'm a Computer Science student and writer. My primary interests are Graph Theory, Number Theory, Programming Language Theory, Logic and Windows Debugging.
This entry was posted in Computer Science, Mathematics, Number Theory. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s