login
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.
4

%I #35 Jan 24 2025 12:14:51

%S 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 44,45,48,49,51,52,57,58,60,61,64,65,67,68,72,73,75,76,79,80,82,83,88,

%U 89,91,92,95,96,98,99,103,104,106,107,110,111,113,114,120,121,123,124,127,128,130

%N 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 Adding a loop at the root makes the graph 3-regular: each vertex has degree 3.

%C The first differences of this sequence give A091090.

%H 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 Wikipedia, <a href="https://en.wikipedia.org/wiki/Chip-firing_game">Chip-firing game</a>.

%F 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 a(n) = 2n-A000120(n)-A070939(n). - _Chai Wah Wu_, Sep 18 2024

%e If there are four chips at the root, then the root fires and the process ends in a stable configuration.

%e 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 a:= n-> (l-> add((2^(i-1)-1)*(l[i]+1), i=2..nops(l)-1))(Bits[Split](2*n+1)):

%p seq(a(n), n=1..70); # _Alois P. Heinz_, Sep 12 2024

%o (Python)

%o def a(n):

%o if n <= 2:

%o return 0

%o else:

%o return (n+1) // 2 - 1 + a((n+1)//2 - 1)

%o print([a(2*n) for n in range(1, 51)])

%o (Python)

%o def A376116(n): return (n<<1)-n.bit_count()-n.bit_length() # _Chai Wah Wu_, Sep 18 2024

%Y Cf. A091090, A376131, A376132, A000120, A070939.

%K nonn

%O 1,3

%A _Ryota Inagaki_, _Tanya Khovanova_, and _Austin Luo_, Sep 10 2024