A305992 -id:A305992 - cp's OEIS frontend

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".

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

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".

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

C

PARI

PARI