Comment concerning A038044, and other convolution sequences.

[Antti Karttunen]

I wrote yesterday:

> Cheers,
>
> here's the first new application of Marc's MASKCONV transformation, the sequence A062177.
> But first the additions to existing ones:
>
> %Y A003095 Cf. A038044.
>
> %Y A038044 Positions of odd terms seems to be given by A003095. Other self-convolved sequences: A000108, A007460 - A007464, A025192, A061922, A062177.

Sorry, more work for you Neil. You can substitute "are" for "seems to be" in the above comment for A038044.
I.e., the results of successive Dirichlet self-convolutions (if we start from the seed-sequence [1]) are always
2*something, unless the length of the current list is square, in which case it is 2*something + A[sqrt(current length)]^2
and that in turn is odd, only if that term A[sqrt(current length)] is odd. So, if there is an odd term at position x
in the A038044, then at least in the position (x^2)+1 there will be another odd term.
So we get A003095: a(n) = a(n-1)^2 + 1 = 1,2,5,26,677,458330,... as the positions of odd terms.



Furthermore, we can add the following comment to A000225 (= (2^n)-1):

%C A000225 This gives the (zero-based) positions of odd terms in the following convolution sequences: A000108, A007460, A007461, A007463, A007464, A061922

(Would anybody like to compute these terms?, i.e. for Catalans we get:
1,1,5,429,9694845,14544636039226909, which is already stored in EIS as A038003)


This is based on observation, that all the convolution functions used here,
i.e. the ordinary multiplication for Catalans, and its "corrupted variants", bitwise-AND, LCM and Xmult for
A007461, A007463 and A061922, as well as bitwise-OR for A007460 and GCD for A007464
produce an odd result _only if at least the other_ of their operands is odd, and thus the result of next convolution iteration
can be odd only if the "central term" of the "previous generation" sequence was odd.

Of course, for the Catalans we get also a purely combinatorial proof.
E.g., if we use the interpretation C_n gives the number of
"rooted plane binary trees with n+1 leaves (2n edges, 2n+1 vertices)"
we get the following five possible planar binary trees:

\/
 \/    (and its mirror image)
  \/

  \/
 \/    (and its mirror image)
  \/

\/ \/
 \./

and this last, symmetric tree is one which makes the result odd.
(And similar palindromic trees may occur only when there are 2^n leaves).



Comment to Marc:

One could create all kind of hybrid-convolution sequences:
I.e. where the indexing is as with Dirichlet convolution or Mask convolution,
but the applied function is not ordinary multiplication, but one of the above
ones as in A007460-A007464 or A061922.
Or like Dirichlet convolution (or MOBIUS inverse transform), but the
applied condition of divisibility is as GF(2)[X] polynomial multiplication.
(i.e., the two indices i and j, must Xmult(i,j) = n, the position of term to
be computed).


Terveisin,

Antti Karttunen