login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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". 1
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

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.

LINKS

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

Wikipedia, Cellular automaton

Wikipedia, Floor and ceiling functions

EXAMPLE

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 ]

           |    |    |    |    |

          ...  ...  ...  ...  ...

PROG

(C)

#include <stdio.h>

#include <string.h>

#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"); }

(PARI) 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

(PARI) 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

CROSSREFS

Cf. A305992, A088803.

Sequence in context: A184742 A232499 A246705 * A024672 A091555 A184398

Adjacent sequences:  A300994 A300995 A300996 * A300998 A300999 A301000

KEYWORD

nonn

AUTHOR

Luc Rousseau, Jun 14 2018

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 16 03:58 EDT 2022. Contains 353688 sequences. (Running on oeis4.)