PHP McNugget Number Checker

[x BlueRobot]

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}.

#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]

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]

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

 

[niemiro]

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]

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:

#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);
  }
}

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[i]) return 0;
  return 1;
}

 

[Laxer]

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]

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]

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. :)