cp's OEIS Frontend

A088803 a(n) gives the number of steps taken in a process which manipulates piles of tokens arranged in a line. There are 2n (or 2n+1) tokens in all. Initially they are all in one pile. At each step every pile with more than 1 token is divided into two and half the token are added to the pile on the left and half to the pile on the right. If a pile has an odd number of tokens, the token left over stays where it is. The redistributions in each step are done in parallel.

%I A088803 #14 Jul 03 2018 18:13:52
%S A088803 1,3,7,11,17,25,33,41,53,65,77,93,109,123,143,163,181,203,227,249,277,
%T A088803 303,329,357,389,417,451,485,517,555,593,629,669,711,749,795,839,883,
%U A088803 931,981,1025,1077,1131,1179,1235,1293,1343,1403,1465,1519,1583,1649
%N A088803 a(n) gives the number of steps taken in a process which manipulates piles of tokens arranged in a line. There are 2n (or 2n+1) tokens in all. Initially they are all in one pile. At each step every pile with more than 1 token is divided into two and half the token are added to the pile on the left and half to the pile on the right. If a pile has an odd number of tokens, the token left over stays where it is. The redistributions in each step are done in parallel.
%H A088803 R. Anderson, L. Lovász, P. Shor, J. Spencer, E. Tardos, S. Winograd, <a href="http://www.jstor.org/stable/2323970">Disks, balls and walls: analysis of a combinatorial game</a>, Amer. Math. Monthly, 6, 96, pp. 481-493, 1989.
%F A088803 The sequence is asymptotically quadratic with a(n) ~= c*n^2, where c is between 0.33 and 0.65, with estimate 0.5973 for n = 10000.
%e A088803 E.g., a(2) = 3 because there are 3 steps in the process beginning with 4 tokens:
%e A088803 0 0 4 0 0
%e A088803 0 2 0 2 0
%e A088803 1 0 2 0 1
%e A088803 1 1 0 1 1
%o A088803 (C)
%o A088803 #include <stdio.h>
%o A088803 #include <string.h>
%o A088803 #define N 1000
%o A088803 #define NN (2 * (N / 2) + 1)
%o A088803 void e(int *t, int *T) {
%o A088803     int i;
%o A088803     for (i = 0; i < NN; i ++) {
%o A088803         T[i] += (t[i] % 2); int f = (t[i] / 2);
%o A088803         if (f) { T[i - 1] += f; T[i + 1] += f; }
%o A088803     }
%o A088803 }
%o A088803 int f(int n) {
%o A088803     int t[NN], T[NN], i = 0;
%o A088803     memset(t, 0, sizeof(t)); memset(T, 0, sizeof(T));
%o A088803     t[N / 2] = n; e(t, T);
%o A088803     while (memcmp(t, T, sizeof(t)) != 0) { i ++; memcpy(t, T, sizeof(T)); memset(T, 0, sizeof(T)); e(t, T); }
%o A088803     return i;
%o A088803 }
%o A088803 int main() { int n; for (n = 2; n <= N; n += 2) { printf("%d, ", f(n)); fflush(stdout); } printf("\n"); }
%o A088803 /* _Luc Rousseau_, Jun 29 2018 */
%Y A088803 Cf. A088804.
%K A088803 nonn
%O A088803 1,2
%A A088803 _Rob Arthan_, Oct 17 2003