A088803 -id:A088803 - cp's OEIS frontend

A088804 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, from each pile with more than 1 token, one token is taken and added to the pile on its left and one is taken and added to the pile on its right. The redistributions in each step are done in parallel.

1, 4, 8, 14, 21, 29, 39, 51, 63, 77, 93, 110, 128, 148, 170, 192, 216, 242, 268, 296, 326, 358, 390, 424, 460, 496, 534, 574, 615, 657, 701, 747, 793, 841, 891, 941, 993, 1047, 1103, 1159, 1217, 1277, 1337, 1399, 1463, 1529, 1595, 1663, 1733, 1803, 1875, 1949

Offset: 1

Rob Arthan, Oct 17 2003

nonn

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

R. Anderson, L. Lovasz, 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.
Anders Björner, László Lovászb, Peter W. Shor, Chip-firing games on graphs, European Journal of Combinatorics 12, pp. 283-291, 1991.
Mikkel Thorup, Firing Games

Cf. A088803.

The sequence is asymptotically quadratic with a(n) ~= c*n^2, where c is between 0.33 and 1, with estimate 0.7078 for n = 1, 000.

A300997 a(n) is the number of steps needed to reach a stable configuration in the 1D cellular automaton initialized with one cell with mass n and based on the rule "each cell gives half of its mass, rounded down, to its right neighbor".

Original entry on oeis.org

0, 1, 3, 4, 6, 8, 10, 11, 13, 15, 17, 19, 21, 23, 24, 26, 28, 30, 32, 34, 36, 38, 40, 41, 43, 45, 47, 49, 51, 53, 55, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 87, 89, 91, 93, 95, 97, 99, 101, 103, 105, 107, 109, 111, 113, 114, 116, 118, 120, 122, 124, 126, 128

Offset: 1

Luc Rousseau, Jun 14 2018

nonn

The cellular automaton is initialized with 1 cell with mass n. The evolution rule consists of each cell keeping half of its mass, rounded up (ceiling(mass / 2)), and giving half of its mass, rounded down (floor(mass / 2)), to its right neighbor. a(n) is the number of steps needed to reach the stable configuration made of n cells with mass 1.

Observations/conjectures: it appears that the finite difference of this sequence only contains 1's and 2's, that the runs of 2's are delimited by isolated 1's and tend to become larger and larger. One can probably write a(n) = 2*n - Sum_{k=1..n} I(k) where I(n) is the indicator function of some other sequence. See A305992.

			Diagram illustrating a(5) = 6:
    0    [ 5 ]        <-- initial configuration
           | \
           3  2
           |   \
    1    [ 3 ][ 2 ]
           | \  | \
           2  1 1  1
           |   \|   \
    2    [ 2 ][ 2 ][ 1 ]
           | \  | \  |
           1  1 1  1 1
           |   \|   \|
    3    [ 1 ][ 2 ][ 2 ]
           |    | \  | \
           1    1  1 1  1
           |    |   \|   \
    4    [ 1 ][ 1 ][ 2 ][ 1 ]
           |    |    | \  |
           1    1    1  1 1
           |    |    |   \|
    5    [ 1 ][ 1 ][ 1 ][ 2 ]
           |    |    |    | \
           1    1    1    1  1
           |    |    |    |   \
    6    [ 1 ][ 1 ][ 1 ][ 1 ][ 1 ] <-- stable
           |    |    |    |    |
           1    1    1    1    1
           |    |    |    |    |
    7    [ 1 ][ 1 ][ 1 ][ 1 ][ 1 ]
           |    |    |    |    |
          ...  ...  ...  ...  ...

Wikipedia, Cellular automaton
Wikipedia, Floor and ceiling functions

Cf. A305992, A088803.

#include 
#include 
#define N 100
void e(int *t, int *s) {
  int T[N], i = 0; memset(T, 0, sizeof(T));
  while (i < *s) {
    int f = t[i] / 2;
    T[i] += f + (t[i] % 2);
    T[++ i] += f;
  }
  if (T[*s] != 0) { *s += 1; }
  for (i = 0; i < *s; i ++) { t[i] = T[i]; }
}
int a(int n) {
  int t[N], s = 1, i = 0; t[0] = n;
  while (s != n) { i ++; e(t, &s); }
  return i;
}
int main() { int n; for (n = 1; n <= N; n ++) { printf("%d, ", a(n)); } printf("\n"); }

do(v) = {keep = vector(#v, k, ceil(v[k]/2)); move = vector(#v, k, floor(v[k]/2)); nv = vector(#v+1, k, if (k<=#v, keep[k], 0) + if (k==1, 0, move[k-1])); if (nv[#nv]==0, nv = vector(#nv-1, k, nv[k])); nv;}
a(n) = {vs = [n]; vend = vector(n, k, 1); nb = 0; while(vs != vend, vs = do(vs); nb++); nb;} \\ Michel Marcus, Jul 02 2018

a(n) = {my(v=[n], res=0); while(Set(v)!=[1], res++; v = concat([ceil(v[1] / 2), vector(#v-1, i, v[i]\2 + ceil(v[i+1]/2)), vector(v[#v] > 1, k, v[#v] \ 2)])); res} \\ David A. Corneth, Jul 03 2018

cp's OEIS Frontend

Views

Author

Keywords

Examples

Links

Crossrefs

Formula