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
Keywords
Examples
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.
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.
Programs
-
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
-
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)])
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.
Comments