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.

%I A376116 #43 Aug 22 2025 13:26:58
%S A376116 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,
%T A376116 44,45,48,49,51,52,57,58,60,61,64,65,67,68,72,73,75,76,79,80,82,83,88,
%U A376116 89,91,92,95,96,98,99,103,104,106,107,110,111,113,114,120,121,123,124,127,128,130
%N 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.
%C A376116 Adding a loop at the root makes the graph 3-regular: each vertex has degree 3.
%C A376116 The first differences of this sequence give A091090.
%H A376116 Yifan Xie, <a href="/A376116/b376116.txt">Table of n, a(n) for n = 1..10000</a>
%H A376116 Dillan Agrawal, Selena Ge, Jate Greene, Tanya Khovanova, Dohun Kim, Rajarshi Mandal, Tanish Parida, Anirudh Pulugurtha, Gordon Redwine, Soham Samanta, and Albert Xu, <a href="https://arxiv.org/abs/2501.06675">Chip-Firing on Infinite k-ary Trees</a>, arXiv:2501.06675 [math.CO], 2025. See p. 10.
%H A376116 Ryota Inagaki, Tanya Khovanova, and Austin Luo, <a href="https://doi.org/10.1007/s00026-025-00779-6">On Chip-Firing on Undirected Binary Trees</a>, Ann. Comb. (2025). See p. 22.
%H A376116 Wikipedia, <a href="https://en.wikipedia.org/wiki/Chip-firing_game">Chip-firing game</a>.
%F A376116 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.
%F A376116 a(n) = 2n-A000120(n)-A070939(n). - _Chai Wah Wu_, Sep 18 2024
%e A376116 If there are four chips at the root, then the root fires and the process ends in a stable configuration.
%e A376116 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.
%p A376116 a:= n-> (l-> add((2^(i-1)-1)*(l[i]+1), i=2..nops(l)-1))(Bits[Split](2*n+1)):
%p A376116 seq(a(n), n=1..70);  # _Alois P. Heinz_, Sep 12 2024
%o A376116 (Python)
%o A376116 def a(n):
%o A376116     if n <= 2:
%o A376116         return 0
%o A376116     else:
%o A376116         return (n+1) // 2 - 1 + a((n+1)//2 - 1)
%o A376116 print([a(2*n) for n in range(1, 51)])
%o A376116 (Python)
%o A376116 def A376116(n): return (n<<1)-n.bit_count()-n.bit_length() # _Chai Wah Wu_, Sep 18 2024
%Y A376116 Cf. A091090, A376131, A376132, A000120, A070939.
%K A376116 nonn
%O A376116 1,3
%A A376116 _Ryota Inagaki_, _Tanya Khovanova_, and _Austin Luo_, Sep 10 2024