McNuggets problem

McNuggets problem
You are encouraged to solve this task according to the task description, using any language you may know.

From Wikipedia:

The McNuggets version of the coin problem was introduced by Henri Picciotto,
who included it in his algebra textbook co-authored with Anita Wah. Picciotto
thought of the application in the 1980s while dining with his son at
McDonald's, working the problem out on a napkin. A McNugget number is
the total number of McDonald's Chicken McNuggets in any number of boxes.
In the United Kingdom, the original boxes (prior to the introduction of
the Happy Meal-sized nugget boxes) were of 6, 9, and 20 nuggets.

Task

Calculate (from 0 up to a limit of 100) the largest non-McNuggets number (a number n which cannot be expressed with 6x + 9y + 20z = n where x, y and z are natural numbers).

C

<lang c>#include <stdio.h>

int main() {

   int max = 0, i = 0, sixes, nines, twenties;

loopstart: while (i < 100) {

       for (sixes = 0; sixes*6 < i; sixes++) {
           if (sixes*6 == i) {
               i++;
               goto loopstart;
           }

           for (nines = 0; nines*9 < i; nines++) {
               if (sixes*6 + nines*9 == i) {
                   i++;
                   goto loopstart;
               }

               for (twenties = 0; twenties*20 < i; twenties++) {
                   if (sixes*6 + nines*9 + twenties*20 == i) {
                       i++;
                       goto loopstart;
                   }
               }
           }
       }
       max = i;
       i++;
   }

   printf("Maximum non-McNuggets number is %d\n", max);

   return 0;

}</lang>

REXX

<lang rexx>/*REXX pgm solves the McNuggets problem: the largest McNugget number for given meals. */ parse arg y /*obtain optional arguments from the CL*/ if y= | y="," then y= 6 9 20 /*Not specified? Then use the defaults*/ say 'The number of McNuggets in the serving sizes of: ' space(y) $=

1. = 0 /*the Y list must be in ascending order*/

z=.

      do j=1  for words(y);      _= word(y, j)  /*examine  Y  list for dups, neg, zeros*/
      if _==1               then signal done    /*Value ≡ 1?  Then all values possible.*/
      if _<1                then iterate        /*ignore zero and negative # of nuggets*/
      if wordpos(_, $)\==0  then iterate        /*search for duplicate values.         */
           do k=1  for #                        /*   "    "  multiple     "            */
           if _//word($,k)==0  then iterate j   /*a multiple of a previous value, skip.*/
           end   /*k*/
      $= $ _;      #= # + 1;     $.#= _         /*add─►list; bump counter; assign value*/
      end        /*j*/

if #<2 then signal done /*not possible, go and tell bad news. */ _= gcd($) if _\==1 then signal done /* " " " " " " " */ if #==2 then z= $.1 * $.2 - $.1 - $.2 /*special case, construct the result. */ if z\==. then signal done h= 0 /*construct a theoretical high limit H.*/

      do j=2  for #-1;  _= j-1;       _= $._;       h= max(h, _ * $.j  -  _  -  $.j)
      end   /*j*/

@.=0

      do j=1  for #;    _= $.j                  /*for every value, make as possible.   */
        do k=_  by _  to h;   @.k=1;  end /*k*/ /*populate every multiple as possible. */
      end   /*j*/

      do j=1  for #;    _= $.j                  /*populate the  Jth + Kth   summand.   */
        do k=1  for h;  if \@.k  then iterate
        s= k + _;       @.s= 1                  /*add two #s;   mark as being possible.*/
        end   /*k*/
      end     /*j*/

      do z=h  by -1  for h                      /*find largest integer not summed.     */
      if \@.z  then leave
      end     /*z*/

say done: if z==. then say 'The largest McNuggets number not possible.'

               else say 'The largest McNuggets number is: '          z

exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ gcd: procedure; $=; do j=1 for arg(); $=$ arg(j); end; $= space($)

    parse var $ x $;     x= abs(x);
      do  while $\==;  parse var $ y $;  y= abs(y);  if y==0  then iterate
        do  until y==0;  parse value  x//y  y   with   y  x;  end
      end;              return x<lang>

output   when using the default inputs:

The number of McNuggets in the serving sizes of:  6 9 20

The largest McNuggets number is:  43