login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 56th year, we are closing in on 350,000 sequences, and we’ve crossed 9,700 citations (which often say “discovered thanks to the OEIS”).

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

Alois P. Heinz, Rows n = 1..141, flattened

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

Adjacent sequences:  A180225 A180226 A180227 * A180229 A180230 A180231

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 | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 8 00:04 EST 2021. Contains 349590 sequences. (Running on oeis4.)