login
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.
3
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,3
COMMENTS
Adding a loop at the root makes the graph 3-regular: each vertex has degree 3.
The first differences of this sequence give A091090.
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.
a(n) = 2n-A000120(n)-A070939(n). - Chai Wah Wu, Sep 18 2024
EXAMPLE
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.
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
PROG
(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
CROSSREFS
KEYWORD
nonn
AUTHOR
STATUS
approved