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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A210466 Length of the shortest path to the hardest to obtain volumes in the two jugs problem. 1
2, 4, 4, 6, 6, 8, 6, 8, 8, 10, 10, 10, 10, 12, 8, 10, 12, 14, 14, 12, 14, 16, 10, 12, 12, 14, 14, 16, 16, 18, 18, 16, 16, 20, 12, 14, 14, 16, 16, 18, 18, 20, 20, 22, 22, 16, 18, 20, 22, 24, 14, 16, 20, 20, 24, 26, 26, 18, 20, 22, 22, 24, 26, 28, 16, 18, 18, 20 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

Let's enumerate tuples of numbers (x,y), with x > y, y > 1, gcd(x,y) = 1 and starting with (3,2): (3,2), (4,3), (5,2), (5,3), (5,4), (6,5), (7,2), (7,3), (7,4), (7,5), (7,6), (8,3), (8,5), (8,7), (9,2), ... .

A tuple gives the volume of two jugs. (5,3) means: a 5 liters jug and a 3 liters jug. The jugs do not have graduations. Now try to obtain 4 liters (4 is the goal) by filling (you can use an infinite supply of water) or emptying jugs or pouring a jug into the other. The shortest solution is (5,0) (2,3) (2,0) (0,2) (5,2) (4,3). Its length is 6.

All other volumes from 1 to 5 (all other goals) can be obtained in no more than 6 steps. So, 6 is the length of shortest path to the hardest goal for tuple (5,3). As (5,3) is the tuple number 4 in the list (I tried to use a "natural" order of (x,y) tuples), a(4)=6.

We only considered tuples (x,y) with gcd(x,y)=1 as they are tuples for which all goals from 1 to x can be obtained. In fact, a goal G can be obtained if G is a multiple of gcd(x,y) and G<=x.

Another example: a(14)=12. It means that, for the tuple number 14 (tuple (8,7): an 8 liters jug and a 7 liters one), the length of the solution to the hardest goal is 12. Again, 4 liters is the hardest goal, and the 12 steps to get it are: (0,7) (7,0) (7,7) (8,6) (0,6) (6,0) (6,7) (8,5) (0,5) (5,0) (5,7) (8,4).

Tuple (y+1,y) has solution length 2*(y-1). - Jon Perry, Jan 30 2013

REFERENCES

Chuquet, Triparty en la science des nombres, 1484 (Jeu du tavernier).

Dudeney, Amusements in mathematics, 1917  (The Wassail Bowl).

Guyot, Récréations mathématiques, 1799.

LINKS

Alois P. Heinz, Table of n, a(n) for n = 1..10000

C.-G. Bachet, Problèmes plaisants et délectables qui se font par les nombres, 1610.

Laurent Signac, Problèmes de transvasements

Eric W. Weisstein, MathWorld: Three Jug Problem

EXAMPLE

Table of the first terms:

x\y| 2   3   4   5   6

---+------------------

3  | 2

4  |     4

5  | 4   6   6

6  |             8

7  | 6   8   8  10  10

- Jon Perry, Jan 31 2013

CROSSREFS

Cf. A180227, A180228, A180229 (give the number of steps to obtain volume 1, 2 and 3 using any pair of jugs (x,y), x >= y >= 1 (gcd(x,y) is not necessarily equal to 1)).

Sequence in context: A161794 A111650 A156686 * A085914 A211390 A014684

Adjacent sequences:  A210463 A210464 A210465 * A210467 A210468 A210469

KEYWORD

nonn

AUTHOR

Laurent Signac, Jan 22 2013

EXTENSIONS

More terms from Alois P. Heinz, Jan 29 2013

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 January 29 16:58 EST 2020. Contains 331347 sequences. (Running on oeis4.)