[seqfan] two jug problem

[Dmitry Kamenetsky]

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