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
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 root fires a total of 4 times.
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. 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.
Programs
-
Maple
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
-
Python
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)]) -
Python
def A376116(n): return (n<<1)-n.bit_count()-n.bit_length() # Chai Wah Wu, Sep 18 2024
Formula
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.
Comments