PHP McNugget Number Checker

x BlueRobot · Jan 8, 2015

McNugget Numbers are any integer n, which can be satisfied with the linear combination of 6a + 9b + 20c.

All integers are McNugget Numbers with exception of {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 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}.

Code:

#include <iostream>

int size_6 (int n, int a) {

    a = n / 6;

    return a;
}

int size_9 (int n, int b) {

    b = n / 9;

    return b;

}

int size_20 (int n, int c) {

    c = n / 20;

    return c;
}

int main() {

    int n; //User Input, n to check
    int a, b, c = 0; //number of possible 6, 9 or 20 size boxes to satisify n
    
    std::cout << "Welcome to the McNugget Number Checker.\n";
    std::cout << "Which number would like to check?\n";
    std::cout << "Enter a number: "; 
    std::cin >> n;
    std::cin.ignore();
    
    if (n % 6 == 0) {

        std::cout << "{" << size_6(n,a) << ",0,0}\n";
    }
    else {
        std::cout << n << " can't be satisfied with just a x6 McNugget Box\n";
    }
    
        if (n % 9 == 0) {

            std::cout << "{0," << size_9(n,b) << ",0}\n";
        }
        else {
            std::cout << n << " can't be satisfied with just a x9 McNugget Box\n";
        }
        
    if (n % 20 == 0) {

            std::cout << "{0,0," << size_20(n,c) << "}\n";
        }
        else {
            std::cout << n << " can't be satisified with just a x20 McNugget Box\n";
        }
        
        if (n % 6 != 0 && n % 9 != 0 && n % 20 != 0) {
            
            std::cout << n << " is possibly not a McNugget Number";
        }
    
    std::cin.get();
    return 0;
}

Source: McNugget Number -- from Wolfram MathWorld

Tekno Venus · Jan 8, 2015

That has to be my new favourite type of number! After a very difficult maths mock exam today you've just made my evening. :lol: Why couldn't my maths paper tested me on these numbers?!

x BlueRobot · Jan 8, 2015

Thanks, and I've started a Interesting Number series on my blog too.

niemiro · Jan 8, 2015

For more numbery awesomeness, look up the Encyclopedia of Triangle Centres and don't dare to reference work ethic against anyone other than that guy ever again!

Today's nuggetty bite to chew over....
[sorry. That was abysmal. I'll leave now]. Nice work though!

AceInfinity · Jan 8, 2015

I've designed this small program to test if a number is potentially a McNugget Number

Why "potentially"? The page says this:

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

If you want to use a naive method to check:

Code:

#include <stdio.h>
#include <stdlib.h>

int test(size_t n)
{
  for (size_t i = 0; i <= n; i += 6)
  {
    for (size_t j = 0; i + j <= n; j += 9)
    {
      for (size_t k = 0; i + j + k <= n; k += 20)
      {
        if (i + j + k == n) return 1;
      }
    }
  }
  return 0;
}

int main(void)
{
  for (size_t i = 0; i < 100; ++i)
  {
    if (!test(i)) printf("%u, ", i);
  }
}

Code:

int test(size_t n)
{
  if (n > 43) return 1;
  static int ex[] = { 1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28, 31, 34, 37, 43 };
  for (size_t i = 0; i < sizeof(ex) / sizeof(ex[0]); ++i)
    if (n == ex) return 0;
  return 1;
}

Laxer · Jan 8, 2015

If you want a formal proof this is just another iteration of the postage stamp problem...

You can find many many many proofs online but, here is one from Cornell's website: http://www.cs.cornell.edu/courses/CS4860/2010fa/stamps-problem.pdf

x BlueRobot · Jan 9, 2015

I said potentially because the program only tests if the integer can be satisfied with x amount of one sized box, it doesn't take into account that a integer might use several different amount of all three different box sizes.

AceInfinity · Jan 9, 2015

Yes, but my main idea was showing that there aren't too many numbers that aren't mcnugget numbers, so I can't see why people would want numbers that may potentially be a mcnugget number. Why not go all the way? Nonetheless I'm glad someone is posting some of their code and projects in this section. I never knew what a McNugget number was until I read this. :)

Search

Search

PHP McNugget Number Checker

x BlueRobot

Administrator

Tekno Venus

Senior Administrator, Developer

x BlueRobot

Administrator

niemiro

Senior Administrator, Windows Update Expert

AceInfinity

Emeritus, Contributor

Laxer

Co-Founder
Senior Administrator

x BlueRobot

Administrator

AceInfinity

Emeritus, Contributor

PHP McNugget Number Checker

Administrator

Senior Administrator, Developer

Administrator

Senior Administrator, Windows Update Expert

Emeritus, Contributor

Co-FounderSenior Administrator

Administrator

Emeritus, Contributor

Co-Founder
Senior Administrator