A376132 -id:A376132 - cp's OEIS frontend

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.

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

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.

A378962 First differences of A378726.

Original entry on oeis.org

1, 1, 1, 5, 1, 1, 5, 1, 1, 5, 1, 1, 18, 1, 1, 5, 1, 1, 5, 1, 1, 18, 1, 1, 5, 1, 1, 5, 1, 1, 18, 1, 1, 5, 1, 1, 5, 1, 1, 58, 1, 1, 5, 1, 1, 5, 1, 1, 18, 1, 1, 5, 1, 1, 5, 1, 1, 18, 1, 1, 5, 1, 1, 5, 1, 1, 58, 1, 1, 5, 1, 1, 5, 1

Offset: 1

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

nonn

Sequence A378726(n) is defined to be the total number of fires on a rooted undirected infinite ternary tree with a self-loop at the root, when a chip-firing process starts with 3n chips at the root. The total number of fires for 3n, 3n-1, and 3n-2 chips are the same, so the sequence is defined for one of these three values to remove duplicates.
The corresponding sequence for binary trees is A376132; its distinct values are Eulerian numbers A000295.
The distinct values of this sequence form sequence A000340.

			The total number of fires when starting with 12 chips at the root is 3, and the total number of fires when starting with 15 chips at the root is 8. This means that a(4) = 5.

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.
Wikipedia, Chip-firing game.

Cf. A000295, A000340, A376132, A378724, A378726.

import math
def F(N, k):
    n = int(math.log(N * (k - 1) + 1, k))
    a = [0] * (n + 1)
    num = N - ((k ** n) - 1)/(k - 1)
    for i in range(n, -1, -1):
        if k ** i <= num:
            a[i] = int(num/(k ** i))
            num %= (k ** i)
    res = 0
    for j in range(1, n):
        x = int((j * (k ** (j + 1)) - (j + 1) * (k ** j) + 1)/((k - 1) ** 2))
        res += x * (a[j] + 1)
    return res
s = ""
for N in range(1, 200):
    s += str(int(F(3 * N + 3, 3) - F(3 * N, 3)))
    s += ", "
print(s)

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

cp's OEIS Frontend

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

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

A378962 First differences of A378726.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Formula