A137294 A polynomial-time algorithm for moving all seeds into one pot in a class of sowing positions.

0, 1, 3, 4, 7, 10, 12, 13, 17, 22, 26, 31, 34, 37, 39, 40, 45, 52, 58, 67, 72, 79, 85, 94, 98, 103, 107, 112, 115, 118, 120, 121, 127, 136, 144, 157, 164, 175, 185, 202, 208, 217, 225, 238, 245, 256, 266, 283, 288, 295, 301, 310, 315, 322, 328, 337, 341, 346, 350

Offset: 1

Author

Joshua Zucker, Mar 15 2008

Keywords

• easy
• nonn

Comments

a(n) is asymptotic to O(n^(log base 2 of 3)) according to the reference.

The reference also gives a(2^k) = 1/2 (3^k - 1).

Numerical experiments indicate that a(n) ~ 0.5 or 0.6 * n^(log base 2 of 3). The coefficient seems to oscillate back and forth between 0.5 and 0.6.

The reference also points out that it is possible, by choosing a less efficient recursive algorithm for getting all the seeds in one pot, to simulate the Towers of Hanoi algorithm and obtain 2^(n-1) - 1 moves for a(n) instead.

Examples

			Starting with 1 all the seeds are already in one pot so a(1) = 0 moves.
Starting with 11, move to 2, so a(2) = 1.
Starting with 111, move to 201 and then 012 and then 003, so a(3) = 3 moves.
Starting with 1111, move to 0211, 0202, 0013, 0004, so a(4) = 4 moves.
Starting with 11111, move to 02111, 02102, 03002, 00113, 00203, 00014, 00005, a(5) = 7 moves.
		

References

• J. Erickson, "Sowing Games", in Nowakowski (ed), Games of No Chance, 1996. P. 289 is the most relevant page.

Links

• Joshua Zucker, Table of n, a(n) for n = 1..1000
• J. Erickson, Sowing Games article from Games of No Chance.

Crossrefs

Cf. A000225 is the Towers of Hanoi sequence. A003462 has a(2^n).

Formula

T(1) = 0; T(2m) = 3T(m) + 1; T(2m+1) = 2T(m) + T(m+1) + 2 (from p. 289 of Erickson in Nowakowski reference above).