Take four non-negative integers a,b,c,d with greatest common divisor one. We say that a number n is representable by a,b,c,d if there exist non-negative integers x,y,z,u such that n=ax+by+cz+du.
Question:
This is a case of the so-called knapsack problem. I called this particular instance the platzakprobleem in Dutch. The problem is also known as the Frobenius problem, after the famous mathematician G.Frobenius (1849-1917), who appears to have mentioned the problem repeatedly during his lectures.
The applet above computes the largest non-representable number, and it appears as the last red number in the applet's output. Also, the applet computes the representability of the previous numbers and displays them in yellow (representable) or red (non-representable). At most 500 values are displayed. The input for a,b,c,d should consist of numbers at most three digits long. In principle one can give larger number input, but one takes the risk of long (uninterruptable) times of computation and messy output.
The largest non-representable number for two coefficients a,b (so take c=d=0) is well-known: ab-a-b. For three (take d=0) or more than three numbers the answer is not so simple. A nice starting point in the literature is: J.L.Davison, On the linear diophantine problem of Frobenius, Journal of Number Theory 48 (1994), p353-363.
With the applet one can experiment by taking, for example, values of a,b,c which are related and deduce experimentally a value for the largest non-representable number. The first experiment I did was taking a=n,b=n+1,c=n+2. But of course an infinite amount of variation is possible.
This applet was written as illustration for a lecture held at the Nationale Wiskunde dagen 2001 held in Noordwijkerhout on February 2,3. There is also an accompanying text which, unfortunately for foreigners, is in Dutch.
Author: Frits Beukers, January 2001