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
KEYWORD
easy,nonn
AUTHOR
Joshua Zucker, Mar 15 2008
STATUS
approved