cp's OEIS Frontend

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

%I A137294 #9 Mar 07 2015 06:17:00
%S A137294 0,1,3,4,7,10,12,13,17,22,26,31,34,37,39,40,45,52,58,67,72,79,85,94,
%T A137294 98,103,107,112,115,118,120,121,127,136,144,157,164,175,185,202,208,
%U A137294 217,225,238,245,256,266,283,288,295,301,310,315,322,328,337,341,346,350
%N A137294 A polynomial-time algorithm for moving all seeds into one pot in a class of sowing positions.
%C A137294 a(n) is asymptotic to O(n^(log base 2 of 3)) according to the reference.
%C A137294 The reference also gives a(2^k) = 1/2 (3^k - 1).
%C A137294 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.
%C A137294 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.
%D A137294 J. Erickson, "Sowing Games", in Nowakowski (ed), Games of No Chance, 1996. P. 289 is the most relevant page.
%H A137294 Joshua Zucker, <a href="/A137294/b137294.txt">Table of n, a(n) for n = 1..1000</a>
%H A137294 J. Erickson, <a href="http://compgeom.cs.uiuc.edu/~jeffe/pubs/sowing.html">Sowing Games</a> article from <a href="http://tinyurl.com/2c3mv9">Games of No Chance</a>.
%F A137294 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).
%e A137294 Starting with 1 all the seeds are already in one pot so a(1) = 0 moves.
%e A137294 Starting with 11, move to 2, so a(2) = 1.
%e A137294 Starting with 111, move to 201 and then 012 and then 003, so a(3) = 3 moves.
%e A137294 Starting with 1111, move to 0211, 0202, 0013, 0004, so a(4) = 4 moves.
%e A137294 Starting with 11111, move to 02111, 02102, 03002, 00113, 00203, 00014, 00005, a(5) = 7 moves.
%Y A137294 Cf. A000225 is the Towers of Hanoi sequence. A003462 has a(2^n).
%K A137294 easy,nonn
%O A137294 1,3
%A A137294 _Joshua Zucker_, Mar 15 2008