login
This site is supported by donations 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

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 October 23 23:51 EDT 2019. Contains 328379 sequences. (Running on oeis4.)