OFFSET
1,2
COMMENTS
A definition of the sequence in summary:
n refers to the round number of the tournament, where the finals are 0, semifinals are 1, quarterfinals are 2, etc. Note that the sequence begins at index 1, as f_0 is the empty string.
f_n is a link function, a binary string of n bits, and a(n) is the equivalent integer (shown in decimal). Note that the binary strings of some terms contain leading zeros. The link function pairs matches in the upper and lower brackets of a double elimination tournament (which are also labeled using a binary string of n bits) by a bitwise XOR operation.
LINKS
Chris Shaw, Generating Program
Chris Shaw, Optimising Double Elimination Tournaments and The Effect of Character Choice in Esports (2023), Master's thesis, pp. 29-34.
EXAMPLE
The first 3 terms of the sequence are worked through (with accompanying diagrams) on pages 30 to 33 of the thesis found in the links section.
PROG
(Python) # See linked file oeis.py
(Julia) # after the linked Python program
function nearestparent(round1, round2, link1, link2)
link2 *= 1 << (round1 - round2)
parentround = 0
while parentround <= round2
parent1 = link1 >> (round1 - parentround)
parent2 = link2 >> (round1 - parentround)
if parent1 == parent2
parentround += 1
else break end
end
return parentround - 1 end
function distance(round1, round2, link1, link2)
lowerdist = upperdist = round1 - round2
linkdiff = link1 - (link2 << upperdist)
if !(0 <= linkdiff < (1 << upperdist))
parentround = nearestparent(round1, round2, link1, link2)
dist1 = round1 - parentround
dist2 = round2 - parentround
lowerdist = dist1 + dist2 - 1
end
return upperdist + 2 * lowerdist end
function A356189(maxround::Int = 10)::Vector{Int}
seq = [0]
depth = 2
for round in 2:maxround
step = 2^(round - depth)
conflicts = []
for i in 0:step:(2^round - 1)
distances = []
for j in 1:round - 1
dist = distance(round, j, i, seq[j])
push!(distances, dist)
end
total = sum(1.0 / 2.0^k for k in distances)
push!(conflicts, total * 2.0^round)
end
push!(seq, step * (argmin(conflicts) - 1))
linkbinary = string(seq[end], base=2, pad=round)
depth += linkbinary[depth] == '1' ? 1 : 0
end
return seq end
println(A356189(36)) # Peter Luschny, Nov 28 2023
CROSSREFS
KEYWORD
nonn
AUTHOR
Chris Shaw, Jul 28 2022
STATUS
approved