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.

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

Offset

1,2

Links

Table of n, a(n) for n=1..52.

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. 481-493, 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"); }
/* Luc Rousseau, Jun 29 2018 */

Crossrefs

Cf. A088804.

Sequence in context: A294479 A331968 A029715 * A350146 A194069 A088206

Adjacent sequences: A088800 A088801 A088802 * A088804 A088805 A088806

Keyword

nonn

Author

Rob Arthan, Oct 17 2003

Status

approved