

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.


2



1, 3, 7, 11, 17, 25, 33, 41, 53, 65, 77, 93, 109, 123, 143, 163, 181, 203, 227, 249, 277, 303, 329, 357, 389, 417, 451, 485, 517, 555, 593, 629, 669, 711, 749, 795, 839, 883, 931, 981, 1025, 1077, 1131, 1179, 1235, 1293, 1343, 1403, 1465, 1519, 1583, 1649
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


LINKS

R. Anderson, L. Lovász, P. Shor, J. Spencer, E. Tardos, S. Winograd, Disks, balls and walls: analysis of a combinatorial game, Amer. Math. Monthly, 6, 96, pp. 481493, 1989.


FORMULA

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.


EXAMPLE

E.g., a(2) = 3 because there are 3 steps in the process beginning with 4 tokens:
0 0 4 0 0
0 2 0 2 0
1 0 2 0 1
1 1 0 1 1


PROG

(C)
#include <stdio.h>
#include <string.h>
#define N 1000
#define NN (2 * (N / 2) + 1)
void e(int *t, int *T) {
int i;
for (i = 0; i < NN; i ++) {
T[i] += (t[i] % 2); int f = (t[i] / 2);
if (f) { T[i  1] += f; T[i + 1] += f; }
}
}
int f(int n) {
int t[NN], T[NN], i = 0;
memset(t, 0, sizeof(t)); memset(T, 0, sizeof(T));
t[N / 2] = n; e(t, T);
while (memcmp(t, T, sizeof(t)) != 0) { i ++; memcpy(t, T, sizeof(T)); memset(T, 0, sizeof(T)); e(t, T); }
return i;
}
int main() { int n; for (n = 2; n <= N; n += 2) { printf("%d, ", f(n)); fflush(stdout); } printf("\n"); }


CROSSREFS



KEYWORD

nonn


AUTHOR



STATUS

approved



