A359250 Irregular triangle read by rows where T(n,k) is the coefficient of y^k in polynomial P(n) defined by P(2n) = P(n) and P(2n+1) = y*P(n) + P(n+1) starting P(0) = 0, P(1) = 1.

1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 3, 1, 2, 1, 2, 2, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 1, 3, 1, 3, 3, 1, 2, 1, 3, 4, 1, 2, 2, 1, 2, 2, 2, 1, 1, 1, 3, 3, 1, 2, 2, 1, 2, 3, 2, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5, 1, 4, 1, 4, 4

Offset: 0

Author

Kevin Ryde, Dec 28 2022

Keywords

• nonn
• tabf
• look
• easy

Comments

Row n length is wt(n) = A000120(n), the binary weight of n, so that k ranges 0 <= k < wt(n).

Evaluated at y=1, the recurrence for P is per Stern's diatomic sequence so that row n has sum A002487(n).

Evaluated at y=2, the recurrence for P is per A116528 so that Sum T(n,k)*2^k = A116528(n), and similarly variations such as y=10 for A178243.

Array A178239(r,n) is P(n) evaluated at y=r, and in particular P(n) is the polynomial for the values in column n there.

Column k=1, when that value exists, is T(n,1) = A080791(n-1), the number of 0 bits in n-1, since expressing the recurrence in Q(m) = P(m+1) adds y*Q(m-1) at each 0 bit in m.

Reversing the bits of n is no change to P(n), so that P(n) = P(A030101(n)).

Examples

			Triangle begins:
      k=0  1  2
  n=0:  (empty)
  n=1:  1,
  n=2:  1,
  n=3:  1, 1,
  n=4:  1,
  n=5:  1, 2,
  n=6:  1, 1,
  n=7:  1, 1, 1,
  n=8:  1,
  n=9:  1, 3,
		

Links

• Kevin Ryde, Table of n, a(n) for rows 0..2048, flattened
• Kevin Ryde, PARI/GP Code and Notes
• Thomas Scheuerle, Scatter plot a(n) for n = 1 to 114689. This is in T(n,k) the range of n = 1 to 2^14. It looks a bit like narrow and tall fir trees like you could see in the Schwarzwald region.

Crossrefs

Cf. A000120 (row lengths), A002487 (row sums).

Cf. A178239 (array), A030101 (bit reversal).

Evaluated at y=2..10: A116528, A342633, A342634, A342635, A342603, A342636, A342637, A342638, A178243.

Cf. A125184.

Programs

MATLAB

function a = A359250( max_n )
    ac = cell(1,1); ac{1} = [1];
    for n = 2:max_n
        m = floor(n/2);
        if 2*m == n
            ac{n} = ac{m};
        else
            ac{n} = [ac{m+1} zeros(1,(length(ac{m})+1)-length(ac{m+1}))] ...
            + [0 ac{m}];
        end
    end
    a = cell2mat(ac);
end % Thomas Scheuerle, Dec 28 2022

PARI

\\ See links.

Formula

G.f.: Sum_{n>=0} P(n)*x^n = x * Product_{e>=0} 1 + x^(2^e) + y*x^(2^(e+1)).