A355729 Tournament standing, under standard rules double elimination, of the participant whose elimination leaves n participants still in the tournament.

1, 2, 3, 4, 5, 5, 7, 7, 9, 9, 9, 9, 13, 13, 13, 13, 17, 17, 17, 17, 17, 17, 17, 17, 25, 25, 25, 25, 25, 25, 25, 25, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 65, 65, 65

Offset

0,2

Comments

Standard rules of Double Elimination tournaments lead to equal standings for many players; the farther from the top, the less the placement distinguishes the skill between opponents.

If you were outside a building in which a double elimination tournament was taking place, with N players participating, and each of them walked out of the building the moment they were eliminated, then, using the sequence, you could tell exactly what standing the player exiting the building obtained: If they exit the building k-th then their standing is a(n), where n = N - k.

The last four players to get eliminated in the tournament have the standings of 1, 2, 3, and 4, then there are two 5's that stand for the 5th and the 6th best players, because of that the next number is 7, so there are two 7's, then four 9's and 13's, eight 17's and 25's, sixteen 33's and 49's, and so on.

Links

Table of n, a(n) for n=0..66.

Formula

True definition: A directed tree graph built according to Double Elimination tournament rules is drawn. If any node has the value of n, one of its child nodes copies it, and then their child and so on until there are no more child nodes. The starting node has the value of 1, its child that doesn't have the value of 1 assumes the value of 2. Nodes with values 3 and 4 have obvious placements, but from there there are 2 equally close to the 1 node candidates for 5 and 6. Both of them take the value of 5, and the next unsigned node must take the value of 7. Every other dispute is solved this same way. In the end take the finish nodes, order them in an ascending order according to their value, that's the sequence.

floor(2.5) = 2.

There are two sequences that form this sequence:

a1(n) = 2^floor(log_2(n)) + 1;

{a1(n)} = {1, 2, 3,3, 5,5,5,5, 9, 9, 9, 9, 9, ...};

a2(n) = (3/2)*2^floor(log_2(n)) + 1.

{a2(n)} = {1, 2.5, 4,4, 7,7,7,7, 13,13,13,13,13, ...};

While the target sequence is

{a(n)} = {1, 2, 3,4, 5,5,7,7, 9,9,9,9,13, ...}.

We can use a comparison sequence

a3(n) = a1(n - 2^floor(log_2(n)-1));

{a3(n)} = {1, 1.5, 2,3, 3,3,5,5, 5,5,5,5}.

If a3(n) != a1(n) then a(n) = a1(n), otherwise a(n) = a2(n).

a(n) = {1 if n=0;

a1(n) if a3(n) != a1(n);

a2(n) if a3(n) == a1(n)}.

a(0) = 1, a(n) = n - ((2*n) mod 2^floor(log_2(n)))/2 + 1 for n > 0. - Jon E. Schoenfield, Jul 20 2022

Example

For n = 18:
a1(18) = 2^floor(log_2(18)) + 1 = 2^4 + 1 = 17;
a2(18) = (3/2)*2^floor(log_2(18)) + 1 = (3/2)*16 + 1 = 25;
a3(18) = a1(18 - 2^floor(log_2(18)-1)) = a1(18 - 2^3) = a1(10) = 2^3 + 1 = 9;
a3(18) != a1(18), thus a(18) = a1(18) = 17.

Prog

(Python)
a = lambda n: int(n + 1 - ((2*n) % 2**(n.bit_length()-1))/2)
(PARI) a(n) = 1 + bitand(n, 3<<if(n, logint(n, 2)-1)); \\ Kevin Ryde, Sep 06 2022

Crossrefs

Sequence in context: A086593 A073757 A088468 * A049448 A354547 A130044

Adjacent sequences: A355726 A355727 A355728 * A355730 A355731 A355732

Keyword

easy,nonn

Author

Andrew Mirror, Jul 15 2022

Status

approved