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.

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,3

Comments

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

The first differences of this sequence give A376132.

Links

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.

Formula

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.

Example

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.

Maple

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

Prog

(Python)
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)])

Crossrefs

Cf. A091090, A376116, A376132.

Sequence in context: A047216 A244970 A242330 * A039568 A032926 A214991

Adjacent sequences: A376128 A376129 A376130 * A376132 A376133 A376134

Keyword

nonn

Author

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

Status

approved