function solvable = mcnugget_solvable ( a, b )

%*****************************************************************************80
%
%% mcnugget_solvable() determines whether a McNuggets problem is solvable.
%
%  Discussion:
%
%     We are given a Diophantine equation 
%
%       a1 x1 + a2 x2 + ... + an * xn = b
%
%     for which the coefficients a are positive integers, and
%     the right hand side b is a nonnegative integer.
%
%     We want to know whether there are nonnegative integers x which
%     satisfy this equation.  If so, we say the value b is "solvable". 
%
%     In particular, we might have a = [ 6, 9, 20 ] and b would be
%     the desired number of Chicken McNuggets.
%
%  Licensing:
%
%    This code is distributed under the MIT license.
%
%  Modified:
%
%    29 September 2022
%
%  Author:
%
%    John Burkardt
%
%  Reference:
%
%    Scott Chapman, Chris O’Neill,
%    Factoring in the Chicken McNugget Monoid,
%    Mathematics Magazine, 
%    Volume 91, Number 5, 2018, pages 323-336.
%
%  Input:
%
%    integer a(n): the number of McNuggets in each package size.
%
%    integer b: the total number of McNuggets desired.
%
%  Output:
%
%    boolean solvable: true if there is a solution.
%
  a_num = length ( a );
  solvable = false;
%
%  Check whether b is immediately solvable.
%
  if ( b == 0 ) 
    solvable = true;
    return
  end

  for i = 1 : a_num
    if ( mod ( b, a(i) ) == 0 )
      solvable = true;
      return
    end
  end
%
%  Loop on largest "descendant" of b.
%
  item = [ b ];
  item_num = 1;

  while ( 0 < item_num )

    n = item(item_num);
    item = item(1:item_num-1);
    item_num = item_num - 1;

    for i = 1 : a_num

      n2 = n - a(i);

      if ( n2 == 0 )
        solvable = true;
        return
      end

      if ( 0 <= n2 )

        for j = 1 : a_num
          if ( mod ( n2, a(j) ) == 0 )
            solvable = true;
            return
          end
        end
%
%  Need to update item_num using "length" because n2 might already
%  be in the set...
%
        item = union ( item, n2 );
        item_num = length ( item );

      end

    end

  end

  return
end

