cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

A335756 A cup filling problem starting with 2 empty cups of sizes 3 and n, where a(n) is the number of unreachable states (see details in comments).

This page as a plain text file.
%I A335756 #21 Sep 08 2022 08:46:25
%S A335756 2,0,2,12,6,8,22,12,14,32,18,20,42,24,26,52,30,32,62,36,38,72,42,44,
%T A335756 82,48,50,92,54,56,102,60,62,112,66,68,122,72,74,132,78,80,142,84,86,
%U A335756 152,90,92,162,96,98,172,102,104,182,108,110,192,114,116,202,120,122,212,126,128,222
%N A335756 A cup filling problem starting with 2 empty cups of sizes 3 and n, where a(n) is the number of unreachable states (see details in comments).
%C A335756 Start with 2 empty cups of sizes 3 and n and an unlimited supply of water. For each n, we start with (0,0), which means that both cups are empty, so it takes zero steps to reach that state. We can proceed to other states (i,j) by using one of the 3 operations on each step: "fill", "pour", or "transfer".
%C A335756 (1) To "fill (F)", choose a cup that is not completely full and fill it to its maximum capacity (there is an unlimited supply of water).
%C A335756 (2) To "pour (P)", choose a cup that is not completely empty and pour it all out so that the cup becomes empty.
%C A335756 (3) On a "transfer (T)", one cup is poured into the other. To transfer, choose a nonempty cup to pour from and a nonfull cup to fill up. The amount that is transferred is always the largest possible amount (up to the capacity of the cup being filled).
%C A335756 a(n) gives the number of states, (i,j) with i = 0..3, j = 0..n that cannot be obtained by these operations from (0,0).
%D A335756 B. W. Jackson and D. Thoro, Applied Combinatorics with Problem Solving. Addison-Wesley, Reading, MA, 1990, Chap. 1, pp. 5-6.
%F A335756 a(n) = 2*(n-1)*sign(n mod 3) + (10*floor(n/3)+2)*(1-sign(n mod 3)).
%F A335756 Conjectures from _Colin Barker_, Jun 21 2020: (Start)
%F A335756 G.f.: 2*(1 + x^2 + 4*x^3 + 3*x^4 + 2*x^5) / ((1 - x)^2*(1 + x + x^2)^2).
%F A335756 a(n) = 2*a(n-3) - a(n-6) for n > 5.
%F A335756 (End)
%e A335756 a(4) = 6; for a(4) we have one cup that can hold 3 units of water and another cup that can hold n = 4 units. Starting with empty cups at (0,0), there are fourteen states that can be reached using the given operations. For example, the state (3,2) can be obtained with the sequence (0,0)->(0,4)->(3,1)->(0,1)->(1,0)->(1,4)->(3,2) by the operations F-T-P-T-F-T. However, there are six states (1,1), (2,1), (1,2), (2,2), (1,3) and (2,3) that cannot be obtained from the three operations. So a(4) = 6.
%t A335756 Array[2 #2 (#1 - 1) + (10 Floor[#1/3] + 2)*(1 - #2) & @@ {#, Sign@ Mod[#, 3]} &, 67, 0] (* _Michael De Vlieger_, Jun 28 2020 *)
%o A335756 (Magma) [2*(n-1)*Sign(n mod 3)+(10*Floor(n/3)+2)*(1-Sign(n mod 3)) : n in [0..100]];
%Y A335756 Cf. A335665, A335729, A335843.
%K A335756 nonn,easy
%O A335756 0,1
%A A335756 _Wesley Ivan Hurt_, Jun 20 2020