A356189 Optimal link functions for repeat avoidance in double elimination tournaments.

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

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

Table of n, a(n) for n=1..36.

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

Sequence in context: A248643 A199852 A055978 * A245695 A069025 A356815

Adjacent sequences: A356186 A356187 A356188 * A356190 A356191 A356192

Keyword

nonn

Author

Chris Shaw, Jul 28 2022

Status

approved