A091090 -id:A091090 - cp's OEIS frontend

A135560 a(n) = A007814(n) + A036987(n-1) + 1.

2, 3, 1, 4, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 7, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 8, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 1, 3, 1, 2, 1, 4, 1

Offset: 1

N. J. A. Sloane, Mar 01 2008

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Cf. A007814, A036987, A091090, A135534, A135561.

a[n_] := 1 + IntegerExponent[n, 2] + Sum[(-1)^(n - k - 1)*Binomial[n - 1, k]* Sum[Binomial[k, 2^j - 1], {j, 0, k}], {k, 0, n - 1}]; Table[a[n], {n, 1, 25}] (* G. C. Greubel, Oct 17 2016 *)

a(n)=my(t=valuation(n, 2)); t + (n==2^t) + 1 \\ Charles R Greathouse IV, Oct 17 2016

def A135560(n): return (m:=(~n & n-1)).bit_length()+int(m==n-1)+1 # Chai Wah Wu, Jul 06 2022

a(2^k) = k+2; a(2^k + 2^(k-1)) = k. - Reinhard Zumkeller, Mar 02 2008

More terms from Reinhard Zumkeller, Mar 02 2008

A376116 Number of times the root fires in a chip-firing game starting with 2n chips placed at the root on an infinite binary tree with a loop at the root.

Original entry on oeis.org

0, 1, 2, 4, 5, 7, 8, 11, 12, 14, 15, 18, 19, 21, 22, 26, 27, 29, 30, 33, 34, 36, 37, 41, 42, 44, 45, 48, 49, 51, 52, 57, 58, 60, 61, 64, 65, 67, 68, 72, 73, 75, 76, 79, 80, 82, 83, 88, 89, 91, 92, 95, 96, 98, 99, 103, 104, 106, 107, 110, 111, 113, 114, 120, 121, 123, 124, 127, 128, 130

Offset: 1

Ryota Inagaki, Tanya Khovanova, and Austin Luo, Sep 10 2024

nonn

Adding a loop at the root makes the graph 3-regular: each vertex has degree 3.

The first differences of this sequence give A091090.

			If there are four chips at the root, then the root fires and the process ends in a stable configuration.
If there are eight chips at the root, the root can fire three times, sending 3 chips to each child. After this, each child can fire once. After that the root has 4 chips and can fire again. The root fires a total of 4 times.

Yifan Xie, Table of n, a(n) for n = 1..10000
Dillan Agrawal, Selena Ge, Jate Greene, Tanya Khovanova, Dohun Kim, Rajarshi Mandal, Tanish Parida, Anirudh Pulugurtha, Gordon Redwine, Soham Samanta, and Albert Xu, Chip-Firing on Infinite k-ary Trees, arXiv:2501.06675 [math.CO], 2025. See p. 10.
Ryota Inagaki, Tanya Khovanova, and Austin Luo, On Chip-Firing on Undirected Binary Trees, Ann. Comb. (2025). See p. 22.
Wikipedia, Chip-firing game.

Cf. A091090, A376131, A376132, A000120, A070939.

a:= n-> (l-> add((2^(i-1)-1)*(l[i]+1), i=2..nops(l)-1))(Bits[Split](2*n+1)):
seq(a(n), n=1..70);  # Alois P. Heinz, Sep 12 2024

def a(n):
    if n <= 2:
        return 0
    else:
        return (n+1) // 2 - 1 + a((n+1)//2 - 1)
print([a(2*n) for n in range(1, 51)])

def A376116(n): return (n<<1)-n.bit_count()-n.bit_length() # Chai Wah Wu, Sep 18 2024

a(n) = Sum_{j=1..m-1} (2^j-1)(b(j)+1), where m = floor(log_2(2n+1)) and b(m)b(m-1)...b(1)b(0) is the binary representation of 2*n+1.

a(n) = 2n-A000120(n)-A070939(n). - Chai Wah Wu, Sep 18 2024

A115716 A divide-and-conquer sequence.

Original entry on oeis.org

1, 1, 3, 1, 3, 1, 11, 1, 3, 1, 11, 1, 3, 1, 43, 1, 3, 1, 11, 1, 3, 1, 43, 1, 3, 1, 11, 1, 3, 1, 171, 1, 3, 1, 11, 1, 3, 1, 43, 1, 3, 1, 11, 1, 3, 1, 171, 1, 3, 1, 11, 1, 3, 1, 43, 1, 3, 1, 11, 1, 3, 1, 683, 1, 3, 1, 11, 1, 3, 1, 43, 1, 3, 1, 11, 1, 3, 1, 171, 1, 3, 1, 11, 1, 3, 1, 43, 1, 3, 1, 11, 1

Offset: 0

Paul Barry, Jan 29 2006

			G.f. = 1 + x + 3*x^2 + x^3 + 3*x^4 + x^5 + 11*x^6 + x^7 + 3*x^8 + x^9 + ...

Alois P. Heinz, Table of n, a(n) for n = 0..16381
R. Stephan, Divide-and-conquer generating functions. I. Elementary sequences , arXiv:math/0307027 [math.CO], 2003.

Partial sums are A032925.
Row sums of number triangle A115717.
Bisection: A276390.
Cf. A007583, A081294, A091090.
See A276391 for a closely related sequence.

a:= proc(n) option remember; `if`(n=0, 1,
      `if`(n::odd, 1, 4*a(n/2-1)-1))
    end:
seq(a(n), n=0..100);  # Alois P. Heinz, Sep 07 2016

a[n_] := a[n] = If[n == 0, 1, If[OddQ[n], 1, 4*a[n/2-1]-1]]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Jan 25 2017, after Alois P. Heinz *)

{a(n) = if( n<1, n==0, n%2, 1, 4 * a(n/2-1) - 1)}; /* Michael Somos, Sep 07 2016 */

The g.f. G(x) satisfies G(x)-4*x^2*G(x^2)=(1+2*x)/(1+x). - Argument and offset corrected by Bill Gosper, Sep 07 2016
G.f.: 1/(1-x) + Sum_{k>=0} ((4^k-0^k)/2) *x^(2^(k+1)-2) /(1-x^(2^k)). - corrected by R. J. Mathar, Sep 07 2016
a(n)=A007583(A091090(n+1)-1). - Adapted to new offset by R. J. Mathar, Sep 07 2016
a(0) = 1, a(2*n + 1) = 1 for n>=0. a(2*n + 2) = 4*a(n) - 1 for n>=0. - Michael Somos, Sep 07 2016

A376131 Total number of times all nodes fire in a chip-firing game starting with 2n chips at the root on an infinite binary tree with a loop at the root.

Original entry on oeis.org

0, 1, 2, 6, 7, 11, 12, 23, 24, 28, 29, 40, 41, 45, 46, 72, 73, 77, 78, 89, 90, 94, 95, 121, 122, 126, 127, 138, 139, 143, 144, 201, 202, 206, 207, 218, 219, 223, 224, 250, 251, 255, 256, 267, 268, 272, 273, 330, 331, 335, 336, 347, 348, 352, 353, 379, 380, 384, 385, 396, 397, 401, 402, 522, 523

Offset: 1

Ryota Inagaki, Tanya Khovanova, and Austin Luo, Sep 11 2024

nonn

Adding a loop at the root makes the graph 3-regular: each vertex has degree 3.

The first differences of this sequence give A376132.

			If there are four chips at the root, then the root fires and the process ends in a stable configuration.
If there are eight chips at the root, the root can fire three times, sending 3 chips to each child. After this, each child can fire once. After that the root has 4 chips and can fire again. The total number of fires is 6.

Yifan Xie, Table of n, a(n) for n = 1..10000
Dillan Agrawal, Selena Ge, Jate Greene, Tanya Khovanova, Dohun Kim, Rajarshi Mandal, Tanish Parida, Anirudh Pulugurtha, Gordon Redwine, Soham Samanta, and Albert Xu, Chip-Firing on Infinite k-ary Trees, arXiv:2501.06675 [math.CO], 2025. See p. 13.
Ryota Inagaki, Tanya Khovanova, and Austin Luo, On Chip-Firing on Undirected Binary Trees, Ann. Comb. (2025). See p. 24.
Wikipedia, Chip-firing game.

Cf. A091090, A376116, A376132.

a:= n-> (l-> add(((i-2)*2^(i-1)+1)*(l[i]+1), i=2..nops(l)-1))(Bits[Split](2*n+1)):
seq(a(n), n=1..65);  # Alois P. Heinz, Sep 12 2024

def f0(n):
    if n <= 2:
        return 0
    else:
        return (n+1) // 2 - 1 + f0((n+1)//2 - 1)
def a(n):
    numchip = 2*n
    total = 0
    firetime = f0(numchip)
    l = 0
    while firetime > 0:
        total += (2**l) * firetime
        numchip = (numchip+1)//2 - 1
        firetime = f0(numchip)
        l += 1
    return total
print([a(n) for n in range(1, 66)])

a(n) = Sum_{k=1..m-1}((k-1)*2^k+1)(b(k)+1), where m = floor(log_2(2*n+1)) and b(m)b(m-1)b(m-2)...b(1)b(0) is a binary representation of 2*n+1 in m+1 bits.

A135561 a(n) = 2^A135560(n) - 1.

Original entry on oeis.org

3, 7, 1, 15, 1, 3, 1, 31, 1, 3, 1, 7, 1, 3, 1, 63, 1, 3, 1, 7, 1, 3, 1, 15, 1, 3, 1, 7, 1, 3, 1, 127, 1, 3, 1, 7, 1, 3, 1, 15, 1, 3, 1, 7, 1, 3, 1, 31, 1, 3, 1, 7, 1, 3, 1, 15, 1, 3, 1, 7, 1, 3, 1, 255, 1, 3, 1, 7, 1, 3, 1, 15, 1, 3, 1, 7, 1, 3, 1, 31, 1, 3, 1, 7, 1, 3, 1, 15, 1, 3, 1, 7, 1, 3, 1, 63, 1, 3

Offset: 1

N. J. A. Sloane, Mar 01 2008

R. Zumkeller, Table of n, a(n) for n = 1..10000

Cf. A007814, A036987, A091090, A135534, A135560.

f[n_] := 1 + IntegerExponent[n, 2] + Sum[(-1)^(n - k - 1)*Binomial[n - 1, k]* Sum[Binomial[k, 2^j - 1], {j, 0, k}], {k, 0, n - 1}]; Table[2^f[k] - 1, {k, 1, 20}] (* G. C. Greubel, Oct 17 2016 *)

def A135561(n): return (1<<(m:=(~n & n-1)).bit_length()+int(m==n-1)+1)-1 # Chai Wah Wu, Jul 06 2022

a(2^k) = 2^(k+2) - 1; a(2^k + 2^(k-1)) = 2^k - 1. - Reinhard Zumkeller, Mar 02 2008

More terms from Reinhard Zumkeller, Mar 02 2008

A376132 First differences of A376131.

Original entry on oeis.org

1, 1, 4, 1, 4, 1, 11, 1, 4, 1, 11, 1, 4, 1, 26, 1, 4, 1, 11, 1, 4, 1, 26, 1, 4, 1, 11, 1, 4, 1, 57, 1, 4, 1, 11, 1, 4, 1, 26, 1, 4, 1, 11, 1, 4, 1, 57, 1, 4, 1, 11, 1, 4, 1, 26, 1, 4, 1, 11, 1, 4, 1, 120, 1, 4, 1, 11, 1, 4, 1, 26, 1, 4, 1, 11, 1, 4, 1, 57, 1, 4, 1, 11, 1, 4, 1, 26, 1

Offset: 1

Ryota Inagaki, Tanya Khovanova, and Austin Luo, Sep 11 2024

nonn

The sequence consists of Eulerian numbers from A000295.

The total number of fires for 2n and 2n-1 chips is the same, this is why the interesting increase is 2.

Dillan Agrawal, Selena Ge, Jate Greene, Tanya Khovanova, Dohun Kim, Rajarshi Mandal, Tanish Parida, Anirudh Pulugurtha, Gordon Redwine, Soham Samanta, and Albert Xu, Chip-Firing on Infinite k-ary Trees, arXiv:2501.06675 [math.CO], 2025. See p. 17.
Ryota Inagaki, Tanya Khovanova, and Austin Luo, On Chip-Firing on Undirected Binary Trees, Ann. Comb. (2025). See p. 24.
Wikipedia, Chip-firing game.

Cf. A000295, A091090, A376116, A376131.

b:= n-> (l-> add(((i-2)*2^(i-1)+1)*(l[i]+1), i=2..nops(l)-1))(Bits[Split](2*n+1)):
a:= n-> b(n+1)-b(n):
seq(a(n), n=1..88);  # Alois P. Heinz, Sep 12 2024

a(n) = A000295(A376116(n+1) - A376116(n) + 1).

A085588 Eventual period of a single cell in rule 150 cellular automaton in a cyclic universe of width n.

Original entry on oeis.org

1, 2, 3, 1, 7, 4, 7, 6, 31, 2, 21, 14, 15, 8, 15, 14, 511, 12, 63, 62, 2047, 4, 1023, 42, 511, 28, 16383, 30, 31, 16, 31, 30, 4095, 28, 29127, 1022, 4095, 24, 1023, 126, 127, 124, 4095, 4094, 8388607, 8, 2097151, 2046, 255, 84, 67108863, 1022, 1048575, 56, 511, 32766, 536870911, 60, 17043521, 62, 63, 32, 63, 62

Offset: 3

N. J. A. Sloane, Jul 03 2003

nonn

From Roman Khrabrov, Aug 17 2024: (Start)
It appears that 2^A007814(n) * (2^A309786(n) - 1) divides a(n). For rule 90, it follows from Lemma 3.5 and Theorem 3.5 from Martin & Odlyzko & Wolfram's paper, and the definition of A309786. Rule 150 appears to have the same behavior (verified for n <= 1000).
The numbers for which a(n) differs from 2^A007814(n) * (2^A309786(n) - 1), are the powers of 2 and the numbers in the form 6*2^k, 13*2^k, 37*2^k, 61*2^k, 67*2^k, 95*2^k and so on (there is no corresponding OEIS sequence).
It seems that in 2D case (totalistic rule 34 on a toroidal grid) the formula 2^A007814(n) * (2^A309786(n) - 1) gives the correct maximum cycle lengths in all cases except powers of 2. Replacing A007814(n) with A091090(n) appears to always provide the correct maximum cycle lengths, even at powers of 2.
Conjecture: a(n) = n only if n belongs to A115770. The inverse does not hold true in general; the first exception is 445. (End)

O. Martin, A. M. Odlyzko and S. Wolfram, Algebraic properties of cellular automata, Comm Math. Physics, 93 (1984), pp. 219-258, Reprinted in Theory and Applications of Cellular Automata, S Wolfram, Ed., World Scientific, 1986, pp. 51-90 and in Cellular Automata and Complexity: Collected Papers of Stephen Wolfram, Addison-Wesley, 1994, pp. 71-113 See Table 1.

Roman Khrabrov, Table of n, a(n) for n = 3..1000
Shin-ichi Tadaki, Orbits in one-dimensional finite linear cellular automata, arXiv:cond-mat/9305012, 1993.

Cf. A085587-A085595.

More terms from Sean A. Irvine, Jun 10 2018

Name clarified by Roman Khrabrov, Aug 17 2024

A378725 a(n) = A378724(n+1) - A378724(n).

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 3, 1, 1, 2, 1, 1, 2, 1, 1, 3, 1, 1, 2, 1, 1, 2, 1, 1, 3, 1, 1, 2, 1, 1, 2, 1, 1, 4, 1, 1, 2, 1, 1, 2, 1, 1, 3, 1, 1, 2, 1, 1, 2, 1, 1, 3, 1, 1, 2, 1, 1, 2, 1, 1, 4, 1, 1, 2, 1, 1, 2, 1, 1, 3, 1, 1, 2, 1, 1, 2, 1, 1, 3, 1, 1, 2, 1, 1, 2, 1, 1, 4, 1, 1, 2, 1, 1, 2, 1, 1, 3

Offset: 1

Tanya Khovanova and the MIT PRIMES STEP senior group, Dec 05 2024

nonn

a(n) is the number of root fires on a rooted undirected infinite ternary tree with a self-loop at the root, when the chip-firing process starts with 3(n+1) chips at the root minus the number of root fires in the same tree, when a chip-firing process starts with 3n chips at the root.

The order of the firings doesn't affect the number of firings.

			Suppose we start with 12 chips at the root. Then the root will fire 3 times, 12 chips in total, 3 of which return to the root. The stable configuration will have 3 chips at the root and at every child of the root. Thus, the root fires 3 times in total.
Suppose we start with 15 chips at the root. Then the root will fire 3 times, sending away 9 chips. Then the root can fire again, sending away 3 chips and keeping 3 chips. Now, each child of the root has four chips, and they can also fire. Firing them returns three chips to the root. Thus, the root can fire one more time. The stable configuration will have 3 chips at the root and 1 chip at each child and grandchild. Thus, the root fires 5 times. It follows that a(4) = 5-3 = 2.

The difference sequence for binary trees is A091090.

Dillan Agrawal, Selena Ge, Jate Greene, Tanya Khovanova, Dohun Kim, Rajarshi Mandal, Tanish Parida, Anirudh Pulugurtha, Gordon Redwine, Soham Samanta, and Albert Xu, Chip-Firing on Infinite k-ary Trees, arXiv:2501.06675 [math.CO], 2025. See p. 11.
Wikipedia, Chip-firing game.

Cf. A091090, A378724, A378726, A378727, A378728.

c[n_] := c[n] = Which[n == 1, 1, Mod[n, 3] != 1, 1, True, c[(n - 1)/3] + 1]; Array[c, 103, 1]

cp's OEIS Frontend

A135560 a(n) = A007814(n) + A036987(n-1) + 1.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

A376116 Number of times the root fires in a chip-firing game starting with 2n chips placed at the root on an infinite binary tree with a loop at the root.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Python

Python

Formula

A115716 A divide-and-conquer sequence.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A376131 Total number of times all nodes fire in a chip-firing game starting with 2n chips at the root on an infinite binary tree with a loop at the root.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Python

Formula

A135561 a(n) = 2^A135560(n) - 1.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A376132 First differences of A376131.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

A085588 Eventual period of a single cell in rule 150 cellular automaton in a cyclic universe of width n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions