A378724 - OEIS

%I #18 Jan 24 2025 12:14:41

%S 0,1,2,3,5,6,7,9,10,11,13,14,15,18,19,20,22,23,24,26,27,28,31,32,33,

%T 35,36,37,39,40,41,44,45,46,48,49,50,52,53,54,58,59,60,62,63,64,66,67,

%U 68,71,72,73,75,76,77,79,80,81,84,85,86,88,89,90,92,93,94,98,99,100,102,103,104,106,107

%N The number of root fires on a rooted undirected infinite ternary tree with a self-loop at the root, when the chip-firing process starts with 3n chips at the root.

%C Each vertex of this tree has degree 4. If a vertex has at least 4 chips, the vertex fires and one chip is sent to each neighbor. The root sends 1 chip to its three children and one chip to itself.

%C The order of the firings doesn't affect the number of firings.

%C The corresponding sequence for a binary tree is A376116.

%C The corresponding sequence for a 4-ary tree is A378726.

%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>.

%e Suppose we start with 12 chips at the root. Then the root will fire 3 times, 12 chips total, three of which return to the root. The stable configuration will have 3 chips at the root and at every child of the root. Thus, a(4) = 3.

%e Suppose we start with 15 chips at the root. Then the root fires 3 times, 12 chips total, sending away 9 chips. Then the root can fire again, sending away 3 chips and keeping 3 chips. Now, each child of the root has four chips and can fire, returning to the root three more chips. Thus, the root can fire one more time. The stable configuration will have 3 chips at the root and 1 chip at each child and grandchild. Thus, a(5) = 5.

%o (Python)

%o from math import floor,log

%o def to_base(number, base): # Converts number to a base

%o    digits = []

%o    while number:

%o       digits.append(number % base)

%o       number //= base

%o    return list(digits)

%o def c(m,k,convert): # Calculates the c function

%o    try:

%o       num = to_base(convert,k)[m]

%o    except:

%o       num = 0

%o    return num+1

%o def F(N,k): # Calculated the F function

%o    n = floor(log(N*(k-1)+1)/log(k))

%o    convert = N - int((k**n-1)/(k-1))

%o    ans = 0

%o    for j in range(1,n):

%o       ans += (k**j-1)*c(j,k,convert)

%o    return int(ans/(k-1))

%o seq = []

%o for i in range(1,3*100+1,3): # Change this number to get more terms in the sequence

%o    seq.append(F(i+1,3))

%o print(', '.join(map(str,seq)),end='\n\n')

%Y Cf. A376116, A378725, A378726, A378727, A378728.

%K nonn

%O 1,3

%A _Tanya Khovanova_ and the MIT PRIMES STEP senior group, Dec 05 2024