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,3

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.

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.

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).

Example

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.

Crossrefs

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

Sequence in context: A257508 A221975 A340603 * A282573 A177959 A371634

Adjacent sequences: A137291 A137292 A137293 * A137295 A137296 A137297

Keyword

easy,nonn

Author

Joshua Zucker, Mar 15 2008

Status

approved