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
Keywords
Examples
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
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. 481-493, 1989.
Crossrefs
Cf. A088804.
Programs
-
C
#include
#include #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 */
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.