login
A137294
A polynomial-time algorithm for moving all seeds into one pot in a class of sowing positions.
1
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
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
KEYWORD
easy,nonn
AUTHOR
Joshua Zucker, Mar 15 2008
STATUS
approved