1,3

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.

J. Erickson, "Sowing Games", in Nowakowski (ed) _Games of No Chance_, 1996. p. 289 is the most relevant page.

Joshua Zucker, Table of n, a(n) for n = 1..1000

J. Erickson, Sowing Games article from Games of No Chance.

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

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.

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

Adjacent sequences: A137291 A137292 A137293 this_sequence A137295 A137296 A137297

Sequence in context: A101062 A003669 A047342 this_sequence A108855 A050572 A105343

easy,nonn

Joshua Zucker (joshua.zucker(AT)stanfordalumni.org), Mar 15 2008