prime sig and multiplicative

[Christian G.Bower]

Dave Wilson recently wrote about prime signature sequences and
multiplicative sequences. I recently discovered something
interesting about them.

I was looking at some of my old factorization sequences and found

ID Number: A050377
URL:       http://www.research.att.com/projects/OEIS?Anum=A050377
Sequence:  1,1,1,2,1,1,1,2,2,1,1,2,1,1,1,4,1,2,1,2,1,1,1,2,2,1,2,2,1,1,
           1,4,1,1,1,4,1,1,1,2,1,1,1,2,2,1,1,4,2,2,1,2,1,2,1,2,1,1,1,2,
           1,1,2,6,1,1,1,2,1,1,1,4,1,1,2,2,1,1,1,4,4,1,1,2,1,1,1,2,1,2,
           1,2,1,1,1,4,1,2,2,4,1,1
Name:      Number of ways to factor n into members of A050376.
Comments:  a(n) depends only on prime signature of n (cf. A025487). So a(24)
=
              a(375) since 24=2^3*3 and 375=3*5^3 both have prime signature
(3,1).
           This sequence is very probably multiplicative. - Mitch Harris, Apr
19
              2005
Formula:   Dirichlet g.f.: prod{n in A050376}(1/(1-1/n^s)).

and I noticed Mitch Harris' comment about its multiplicativeness.
(BTW, it is definitely multiplicative, and I didn't notice when I
submitted it.) and it got me to thinking, when is a factorization
sequence multiplicative?  The answer is when the factors are all
prime powers.  (A050376 is number of the form p^2^k).

Now, getting more technical, when I made those factorization sequences
back in 1999, it was because I had just discovered a transform I
call setprod.  There is an example of it in the formula line
without the name.  Basically, if b = setprod(a), treat the sequence
a as a set of integers >1 with multiplicity. (i.e. n is in the set
a_n times).  Then b_n is the number of ways to factor n into elements
of a.  As you might guess from the formula line, b has Dirichlet
generating function as follows:

SUM {n=1 to infinity} b_n/n^s = PROD{n=1 to infinity}(1/(1-a_n/n^s))

I've known for a long time that if a is a prime signature sequence then
so is b.  What I just found out is that b is multiplicative if and only
if a_n=0 for all n that are not prime powers.

This suggests it might be worthwhile to calculate the inverse setprod
of various multiplicative sequences.  I don't think too many of them
will be EIS worthy since all of them have 0's for all non prime power
indices, but they may be worthy of study.

It might be more interesting for those sequences that have a
multiplicative component, but are not actually multiplicative like
A000001 groups.

Oh my, that sequence is actually in the data base.  I guess that
confirms that this is a productive line of reasoning.

ID Number: A090751
URL:       http://www.research.att.com/projects/OEIS?Anum=A090751
Sequence:  0,1,1,1,1,1,1,3,1,1,1,2,1,1,0,8,1,2,1,2,1,1,1,6,1,1,3,1,1,1,
           1,34,0,1,0,4,1,1,1,5,1,2,1,1,0,1,1,23,1,2,0,2,1,6,1,5,1,1,1,
           3,1,1,1,201
Name:      Number of indecomposable groups of order n.
Comments:  Indecomposable means nontrivial and not a direct product of two
proper
              subgroups. Any finite group G is a direct product of
indecomposable
              groups, and the multiset of isomorphism types of indecomposable
              factors is an invariant of G. Hence A000001 has Dirichlet
generating
              function prod((1-n^(-s))^(-a(n)),n>=2).

It's well known that the moebius transform of a multiplicative sequence
is multiplicative.  The moebius transform is just the Dirichlet product
of the sequence with the moebius sequence.  It's also well known that
the Dirichlet product of two multiplicative sequences is multiplicative.
(Since the moebius sequence is multiplicative, the first observation
follows from the second.)

Setprod is exponential relative to the Dirichlet product.

setprod(a+b) = setprod(a) *d setprod(b) where *d is the Dirichlet product
(sequence formed by multiplying the Dirichlet generating functions.)

We now know that the transformed sequences are multiplicative when the
input sequences are 0 in the non prime powers.  When adding the sequences
a and b, if their non prime power indices are 0 they will add to 0, hence
setting up the multiplicative output sequences to Dirichlet product
their way to another multiplicative sequence.

I'll end by describing the inverse setprod of a few well known
multiplicative sequences

A000005 divisors of n
b(p) = 2
b(p^n) = 0, n>1

A000010 totient function phi
0 1 2 1 4 0 6 2 3 0 10 0 12 0 0 3 16 ...
b(p) = p-1
b(p^n), n>1, same as A000022

A000012 all 1's funtion
b(n) = 1 if n prime, 0 otherwise

A000022 a(n)=n
0 2 3 1 5 0 7 2 3 0 11 0 13 0 0 3 17 ...
b(p^n) = number of Lyndon words (aperiodic necklaces) of n
p-colored beads

A000688 abelian groups
b(p^n) = 1

A008683 Moebius function
b(p) = -1
b(p^n) = 0, n>1

A008836 Liouville's lambda function
b(p) = -1
b(p^2) = 1
b(p^n) = 0, n>2

That's enough for now

Christian