A341839 Square array T(n, k), n, k >= 0, read by antidiagonals; for any number m with runs in binary expansion (r_1, ..., r_j), let R(m) = {r_1 + ... + r_j, r_2 + ... + r_j, ..., r_j}; T(n, k) is the unique number t such that R(t) is the union of R(n) and of R(k).

0, 1, 1, 2, 1, 2, 3, 2, 2, 3, 4, 2, 2, 2, 4, 5, 5, 2, 2, 5, 5, 6, 5, 5, 3, 5, 5, 6, 7, 6, 5, 4, 4, 5, 6, 7, 8, 6, 5, 5, 4, 5, 5, 6, 8, 9, 9, 5, 5, 5, 5, 5, 5, 9, 9, 10, 9, 10, 4, 5, 5, 5, 4, 10, 9, 10, 11, 10, 10, 11, 4, 5, 5, 4, 11, 10, 10, 11, 12, 10, 10, 10, 11, 5, 6, 5, 11, 10, 10, 10, 12

Offset: 0

Author

Rémy Sigrist, Feb 21 2021

Keywords

• nonn
• base
• tabl

Comments

For any m > 0, R(m) contains the partial sums of the m-th row of A227736; by convention, R(0) = {}.

The underlying idea is to break in an optimal way the runs in binary expansions of n and of k so that they match, hence the relationship with A003188.

Examples

			Array T(n, k) begins:
  n\k|    0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
  ---+-----------------------------------------------------------------
    0|    0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
    1|    1   1   2   2   5   5   6   6   9   9  10  10  13  13  14  14
    2|    2   2   2   2   5   5   5   5  10  10  10  10  13  13  13  13
    3|    3   2   2   3   4   5   5   4  11  10  10  11  12  13  13  12
    4|    4   5   5   4   4   5   5   4  11  10  10  11  11  10  10  11
    5|    5   5   5   5   5   5   5   5  10  10  10  10  10  10  10  10
    6|    6   6   5   5   5   5   6   6   9   9  10  10  10  10   9   9
    7|    7   6   5   4   4   5   6   7   8   9  10  11  11  10   9   8
    8|    8   9  10  11  11  10   9   8   8   9  10  11  11  10   9   8
    9|    9   9  10  10  10  10   9   9   9   9  10  10  10  10   9   9
   10|   10  10  10  10  10  10  10  10  10  10  10  10  10  10  10  10
   11|   11  10  10  11  11  10  10  11  11  10  10  11  11  10  10  11
   12|   12  13  13  12  11  10  10  11  11  10  10  11  12  13  13  12
   13|   13  13  13  13  10  10  10  10  10  10  10  10  13  13  13  13
   14|   14  14  13  13  10  10   9   9   9   9  10  10  13  13  14  14
   15|   15  14  13  12  11  10   9   8   8   9  10  11  12  13  14  15
		

Links

• Rémy Sigrist, Table of n, a(n) for n = 0..10010
• Rémy Sigrist, Colored representation of the table for n, k < 2^10
• Index entries for sequences related to binary expansion of n

Crossrefs

Cf. A003188, A003987, A005811, A042963, A070939, A101211, A227736, A341840, A341841.

Programs

PARI

T(n,k) = { my (r=[], v=0); while (n||k, my (w=min(valuation(n+n%2,2), valuation(k+k%2,2))); r=concat(w,r); n\=2^w; k\=2^w); for (k=1, #r, v=(v+k%2)*2^r[k]-k%2); v }

Formula

T(n, k) = T(k, n)

T(m, T(n, k)) = T(T(m, n), k).

T(n, n) = n.

T(n, 0) = 0.

A070939(T(n, k)) = max(A070939(n), A070939(k)).

A003188(T(n, k)) = A003188(n) OR A003188(k) (where OR denotes the bitwise OR operator).

T(n, 1) = A042963(ceiling((n+1)/2)).