login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A180228 Triangular array T(A,B) read by rows: minimal number of steps required to obtain exactly 2 liters 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. 3
-1, 1, 1, 2, 2, -1, 4, 2, 6, -1, 4, 2, 2, 6, -1, 4, 2, -1, 2, 6, -1, 4, 2, 8, 8, 2, 6, -1, 4, 2, 4, -1, 6, 2, 6, -1, 4, 2, -1, 10, 12, -1, 2, 6, -1, 4, 2, 10, 4, -1, 6, 12, 2, 6, -1, 4, 2, 6, 12, 10, 12, 16, 10, 2, 6, -1, 4, 2, -1, -1, 4, -1, 6, -1, -1, 2, 6, -1 (list; table; graph; refs; listen; history; text; internal format)
OFFSET
1,4
COMMENTS
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 only if N is a multiple of gcd(A,B).
LINKS
1997 ACM South Central USA programming contest, Problem and Code
Wolfram Mathworld, Three Jug Problem
EXAMPLE
Triangle begins:
-1;
1, 1;
2, 2, -1;
4, 2, 6, -1;
4, 2, 2, 6, -1;
4, 2, -1, 2, 6, -1;
4, 2, 8, 8, 2, 6, -1;
4, 2, 4, -1, 6, 2, 6, -1;
4, 2, -1, 10, 12, -1, 2, 6, -1;
4, 2, 10, 4, -1, 6, 12, 2, 6, -1;
For example T(4,3) = 6.
CROSSREFS
Cf. A180227.
Sequence in context: A325276 A098804 A191320 * A212320 A197376 A113072
KEYWORD
sign,tabl
AUTHOR
Dmitry Kamenetsky, Aug 17 2010
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 16:12 EDT 2024. Contains 371254 sequences. (Running on oeis4.)