A088803 - OEIS

%I #14 Jul 03 2018 18:13:52

%S 1,3,7,11,17,25,33,41,53,65,77,93,109,123,143,163,181,203,227,249,277,

%T 303,329,357,389,417,451,485,517,555,593,629,669,711,749,795,839,883,

%U 931,981,1025,1077,1131,1179,1235,1293,1343,1403,1465,1519,1583,1649

%N 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 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 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 E.g., a(2) = 3 because there are 3 steps in the process beginning with 4 tokens:

%e 0 0 4 0 0

%e 0 2 0 2 0

%e 1 0 2 0 1

%e 1 1 0 1 1

%o (C)

%o #include <stdio.h>

%o #include <string.h>

%o #define N 1000

%o #define NN (2 * (N / 2) + 1)

%o void e(int *t, int *T) {

%o     int i;

%o     for (i = 0; i < NN; i ++) {

%o         T[i] += (t[i] % 2); int f = (t[i] / 2);

%o         if (f) { T[i - 1] += f; T[i + 1] += f; }

%o     }

%o }

%o int f(int n) {

%o     int t[NN], T[NN], i = 0;

%o     memset(t, 0, sizeof(t)); memset(T, 0, sizeof(T));

%o     t[N / 2] = n; e(t, T);

%o     while (memcmp(t, T, sizeof(t)) != 0) { i ++; memcpy(t, T, sizeof(T)); memset(T, 0, sizeof(T)); e(t, T); }

%o     return i;

%o }

%o int main() { int n; for (n = 2; n <= N; n += 2) { printf("%d, ", f(n)); fflush(stdout); } printf("\n"); }

%o /* _Luc Rousseau_, Jun 29 2018 */

%Y Cf. A088804.

%K nonn

%O 1,2

%A _Rob Arthan_, Oct 17 2003