The OEIS mourns the passing of Jim Simons and is grateful to the Simons Foundation for its support of research in many branches of science, including the OEIS.
login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A356189 Optimal link functions for repeat avoidance in double elimination tournaments. 1
0, 2, 0, 4, 24, 56, 64, 160, 192, 448, 256, 2816, 1536, 3584, 18432, 47104, 77824, 159744, 385024, 163840, 360448, 3932160, 8126464, 16515072, 6029312, 63963136, 128974848, 266338304, 524288000, 1069547520, 2071986176, 4211081216, 8438939648, 16240345088, 32614907904, 65364033536 (list; graph; refs; listen; history; text; internal format)
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
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
Sequence in context: A248643 A199852 A055978 * A245695 A069025 A356815
KEYWORD
nonn
AUTHOR
Chris Shaw, Jul 28 2022
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 28 15:56 EDT 2024. Contains 372916 sequences. (Running on oeis4.)