A049773 Triangular array T read by rows: if row n is r(1),...,r(m), then row n+1 is 2r(1)-1,...,2r(m)-1,2r(1),...,2r(m).

1, 1, 2, 1, 3, 2, 4, 1, 5, 3, 7, 2, 6, 4, 8, 1, 9, 5, 13, 3, 11, 7, 15, 2, 10, 6, 14, 4, 12, 8, 16, 1, 17, 9, 25, 5, 21, 13, 29, 3, 19, 11, 27, 7, 23, 15, 31, 2, 18, 10, 26, 6, 22, 14, 30, 4, 20, 12, 28, 8, 24, 16, 32, 1, 33, 17, 49, 9, 41, 25, 57, 5, 37, 21, 53, 13, 45, 29, 61, 3, 35, 19

Offset: 1

Author

Clark Kimberling

Keywords

• nonn
• tabf
• nice
• look

Comments

n-th row = (r(1),r(2),...,r(m)), where m=2^(n-1), satisfies r(r(k))=k for k=1,2,...,m and has exactly 2^[ n/2 ] solutions of r(k)=k. (The function r(k) reverses bits. Or rather, r(k)=revbits(k-1)+1.)

In a knockout competition with m players, arranging the competition brackets (see links) in r(k) order, where k is the rank of the player, ensures that highest ranked players cannot meet until the later stages of the competition. None of the top 2^p ranked players can meet earlier than the p-th from last round of the competition. At the same time the top ranked players in each match meet the highest ranked player possible consistent with this rule. The sequence for the top ranked players meeting the lowest ranked player possible is A131271. - Colin Hall, Jul 31 2011, Feb 29 2012

Row n contains one of A003407(2^(n-1)) non-averaging permutations of [2^(n-1)], i.e., a permutation of [2^(n-1)] without 3-term arithmetic progressions. - Alois P. Heinz, Dec 05 2017

Examples

			Triangle begins:
1;
1,  2;
1,  3, 2,  4;
1,  5, 3,  7, 2,  6,  4,  8;
1,  9, 5, 13, 3, 11,  7, 15, 2, 10,  6, 14, 4, 12,  8, 16;
1, 17, 9, 25, 5, 21, 13, 29, 3, 19, 11, 27, 7, 23, 15, 31, 2, 18, 10, 26, ...
		

Links

• Alois P. Heinz, Rows n = 1..13, flattened
• Eric Weisstein's World of Mathematics, Nonaveraging Sequence.
• Wikipedia, Arithmetic progression.
• Wikipedia, Bracket (tournament).
• Index entries related to non-averaging sequences.

Crossrefs

Sum of odd-indexed terms of n-th row gives A007582. Sum of even-indexed terms gives A049775.

A030109 is another version.

Cf. A131271.

Cf. A088370.

Cf. A003407, A088208.

Programs

Haskell

a049773 n k = a049773_tabf !! (n-1) !! (k-1)
a049773_row n = a049773_tabf !! (n-1)
a049773_tabf = iterate f [1] where
   f vs = (map (subtract 1) ws) ++ ws where ws = map (* 2) vs
-- Reinhard Zumkeller, Mar 14 2015

Maple

T:= proc(n) option remember; `if`(n=1, 1,
      [map(x->2*x-1, [T(n-1)])[], map(x->2*x, [T(n-1)])[]][])
    end:
seq(T(n), n=1..7);  # Alois P. Heinz, Oct 28 2011

Mathematica

row[1] = {1}; row[n_] := row[n] = Join[ 2*row[n-1] - 1, 2*row[n-1] ]; Flatten[ Table[ row[n], {n, 1, 7}]] (* Jean-François Alcover, May 03 2012 *)

PARI

(a(n, k) = if( k<=0 || k>=n, 0, if( k%2, n\2) + a(n\2, k\2))); {T(n, k) = if( k<=0 || k>2^n/2, 0, 1 + a(2^n/2, k-1))}; /* Michael Somos, Oct 13 1999 */