[seqfan] Re: two jug problem

[Charles Greathouse]

I'm not sure how best to represent this.  But I *do* think this is
worth including.  I'm somewhat surprised it's not already in,
actually.

Charles Greathouse
Analyst/Programmer
Case Western Reserve University

On Sat, Aug 7, 2010 at 3:38 AM, Dmitry Kamenetsky
<dmitry.kamenetsky at rsise.anu.edu.au> wrote:
> Dear Sequence Fans,
>
> In the two jug problem we are given two empty jugs with integer liter
> capacities A and B. The task is to measure exactly N integer liters of
> water. You can empty a jug, fill a jug, or you can pour from one jug to the
> other. Pouring stops as soon as the source jug is empty or the destination
> jug is full. Assume that we have an unlimited supply of water.
>
> It is known that the amount N can be made if only if N is a multiple of
> gcd(A,B). Hence if A and B are relatively prime then any amount N can be
> made. Recently I was interested in finding the least number of steps
> (emptying, filling and pouring) required to obtain N from A-liter and
> B-liter jugs. I used the following program to compute the optimal values:
> http://www.ntnu.edu.tw/acm/ProblemSetArchive/B_US_SouthCen/1997/Jugs.html
>
> Now I have two questions. Is this problem interesting enough to be included
> in the OEIS? If so, what is the best way to represent this 3-dimensional
> data? Here are my computed values. First column is A, second column is B,
> third column is N and fourth column is the least number of steps required
> (-1 if impossible). I assume that A>B>=1 and A>=N.
>
>
> Sincerely,
> Dmitry Kamenetsky
>
>
> 2 1 1 2
> 2 1 2 1
> 3 1 1 2
> 3 1 2 2
> 3 1 3 1
> 3 2 1 2
> 3 2 2 2
> 3 2 3 1
> 4 1 1 2
> 4 1 2 4
> 4 1 3 2
> 4 1 4 1
> 4 2 1 -1
> 4 2 2 2
> 4 2 3 -1
> 4 2 4 1
> 4 3 1 2
> 4 3 2 6
> 4 3 3 2
> 4 3 4 1
> 5 1 1 2
> 5 1 2 4
> 5 1 3 4
> 5 1 4 2
> 5 1 5 1
> 5 2 1 4
> 5 2 2 2
> 5 2 3 2
> 5 2 4 4
> 5 2 5 1
> 5 3 1 6
> 5 3 2 2
> 5 3 3 2
> 5 3 4 6
> 5 3 5 1
> 5 4 1 2
> 5 4 2 6
> 5 4 3 6
> 5 4 4 2
> 5 4 5 1
> 6 1 1 2
> 6 1 2 4
> 6 1 3 6
> 6 1 4 4
> 6 1 5 2
> 6 1 6 1
> 6 2 1 -1
> 6 2 2 2
> 6 2 3 -1
> 6 2 4 2
> 6 2 5 -1
> 6 2 6 1
> 6 3 1 -1
> 6 3 2 -1
> 6 3 3 2
> 6 3 4 -1
> 6 3 5 -1
> 6 3 6 1
> 6 4 1 -1
> 6 4 2 2
> 6 4 3 -1
> 6 4 4 2
> 6 4 5 -1
> 6 4 6 1
> 6 5 1 2
> 6 5 2 6
> 6 5 3 10
> 6 5 4 6
> 6 5 5 2
> 6 5 6 1
> 7 1 1 2
> 7 1 2 4
> 7 1 3 6
> 7 1 4 6
> 7 1 5 4
> 7 1 6 2
> 7 1 7 1
> 7 2 1 6
> 7 2 2 2
> 7 2 3 4
> 7 2 4 4
> 7 2 5 2
> 7 2 6 6
> 7 2 7 1
> 7 3 1 4
> 7 3 2 8
> 7 3 3 2
> 7 3 4 2
> 7 3 5 8
> 7 3 6 4
> 7 3 7 1
> 7 4 1 6
> 7 4 2 8
> 7 4 3 2
> 7 4 4 2
> 7 4 5 8
> 7 4 6 6
> 7 4 7 1
> 7 5 1 10
> 7 5 2 2
> 7 5 3 6
> 7 5 4 6
> 7 5 5 2
> 7 5 6 10
> 7 5 7 1
> 7 6 1 2
> 7 6 2 6
> 7 6 3 10
> 7 6 4 10
> 7 6 5 6
> 7 6 6 2
> 7 6 7 1
> 8 1 1 2
> 8 1 2 4
> 8 1 3 6
> 8 1 4 8
> 8 1 5 6
> 8 1 6 4
> 8 1 7 2
> 8 1 8 1
> 8 2 1 -1
> 8 2 2 2
> 8 2 3 -1
> 8 2 4 4
> 8 2 5 -1
> 8 2 6 2
> 8 2 7 -1
> 8 2 8 1
> 8 3 1 8
> 8 3 2 4
> 8 3 3 2
> 8 3 4 10
> 8 3 5 2
> 8 3 6 4
> 8 3 7 8
> 8 3 8 1
> 8 4 1 -1
> 8 4 2 -1
> 8 4 3 -1
> 8 4 4 2
> 8 4 5 -1
> 8 4 6 -1
> 8 4 7 -1
> 8 4 8 1
> 8 5 1 8
> 8 5 2 6
> 8 5 3 2
> 8 5 4 12
> 8 5 5 2
> 8 5 6 6
> 8 5 7 8
> 8 5 8 1
> 8 6 1 -1
> 8 6 2 2
> 8 6 3 -1
> 8 6 4 6
> 8 6 5 -1
> 8 6 6 2
> 8 6 7 -1
> 8 6 8 1
> 8 7 1 2
> 8 7 2 6
> 8 7 3 10
> 8 7 4 14
> 8 7 5 10
> 8 7 6 6
> 8 7 7 2
> 8 7 8 1
>
>
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>