%I #10 Nov 23 2016 23:04:56

%S 1,2,-1,2,2,-1,2,-1,2,-1,2,4,6,2,-1,2,-1,-1,-1,2,-1,2,6,4,6,10,2,-1,2,

%T -1,8,-1,8,-1,2,-1,2,8,-1,4,6,-1,14,2,-1,2,-1,6,-1,-1,-1,10,-1,2,-1,2,

%U 10,10,8,4,6,8,12,18,2,-1

%N Triangular array T(A,B) read by rows: minimal number of steps required to obtain exactly 1 liter in jug A (irrespective of jug B), starting with infinite supply of water and two empty jugs with capacities A and B liters. -1 if not possible. A>=B>=1.

%C In the two-jug problem we are given an infinite supply of water and two empty jugs with integer liter capacities A and B, A>=B>=1. We must use the least number of steps to measure exactly N integer liters of water in jug A, irrespective of jug B. Each step is one of the following: empty a jug, fill a jug, or pour from one jug to the other. Pouring stops as soon as the source jug is empty or the destination jug is full. It is known that the amount N can be made if and only if N is a multiple of gcd(A,B).

%H Alois P. Heinz, <a href="/A180227/b180227.txt">Rows n = 1..141, flattened</a>

%H 1997 ACM South Central USA programming contest, <a href="http://www.ntnu.edu.tw/acm/ProblemSetArchive/B_US_SouthCen/1997/Jugs.html">Problem and Code</a>

%H Wolfram Mathworld, <a href="http://mathworld.wolfram.com/ThreeJugProblem.html">Three Jug Problem</a>

%e Triangle begins:

%e 1;

%e 2, -1;

%e 2, 2, -1;

%e 2, -1, 2, -1;

%e 2, 4, 6, 2, -1;

%e 2, -1, -1, -1, 2, -1;

%e 2, 6, 4, 6, 10, 2, -1;

%e 2, -1, 8, -1, 8, -1, 2, -1;

%e 2, 8, -1, 4, 6, -1, 14, 2, -1;

%e 2, -1, 6, -1, -1, -1, 10, -1, 2, -1;

%K sign,tabl

%O 1,2

%A _Dmitry Kamenetsky_, Aug 17 2010