Multiplicative sequences

[David W. Wilson]

------------------------------------------------------------------------
I was working on the "more" sequences, and wanted to make some notes
about multiplicative sequences in the EIS.

When we say

    a is multiplicative

we understand that

    a(n) = PROD(a(p^e)) where n = PROD(p^e) is the prime factorization of n.

When we say

    a is multiplicative with a(p^e) = [formula in p and e]

(understanding that p is prime and e >= 1), we have fully specified a.  It
then seems to me redundant and obfuscatory to give explanations of what
multiplicative means and/or to provide formulae which follow directly from
the fact that a is multiplicative (and in effect restate that fact).

An case in point is A000252.  Its current state in the EIS:

%I A000252
%S A000252 1,6,48,96,480,288,2016,1536,3888,2880,13200,4608,26208,12096,
%T A000252 23040,24576,78336,23328,123120,46080,96768,79200,267168,
%U A000252 73728,300000
%N A000252 Invertible 2 X 2 matrices mod n.
%C A000252 For a prime p, a(p) = (p^2 - 1)*(p^2 - p) (this is the order of GL(2,
p)). More generally a(n) is multiplicative: if the canonical factorization of n
is the product of p^e(p) over primes p then a(n) = product ((p^(2*e(p)) - p^(2*e
(p) - 2)) * (p^(2*e(p)) - p^(2*e(p) - 1))). - Brian Wallace (brianewallace at hotma
il.com), Apr 05 2001, Dan Fux (danfux at my-deja.com), Apr 18 2001
%F A000252 a(n) = n^4 * product (1-1/p^2)*(1-1/p) = n^4 * product p^(-3)(p^2 - 1
)*(p - 1) where the product is over all the primes p that divide n. - Dan Fux (d
anfux at my-deja.com), Apr 18 2001
%Y A000252 The number of 2 X 2 matrices mod n with determinant 1 is A000056. The
 order of GL_2(K) for a finite field K is in sequence A059238.
%K A000252 nonn,easy,more,nice
%O A000252 1,2
%A A000252 njas

The "meat" of the %C and %F lines are:

    - a is multiplicative with a(p^e) = (p-1)^2*p^(4e-3)*(p+1).
    - For p prime, a(p) = (p-1)^2*p*(p+1) is the order of GL(2,p).
A copy of my last message, which apparently lost some lines.



Note also that this sequences is missing the "mult" keyword.

Here I present my candidate for a leaner, meaner, fully-extended A000252,
with proper attribution for all the observations:

%I A000252
%S A000252 1,6,48,96,480,288,2016,1536,3888,2880,13200,4608,26208,12096,23040,
%T A000252 24576,78336,23328,123120,46080,96768,79200,267168,73728,300000,157248
,
%U A000252 314928,193536,682080,138240,892800,393216,633600,470016,967680,373248
%N A000252 Invertible 2 X 2 matrices mod n.
%C A000252 For p prime, a(p) = (p-1)^2*p*(p+1) = order of GL(2,p) - Brian Wallac
e (brianewallace at hotmail.com), Apr 05 2001
%F A000252 Multiplicative with a(p^e) = (p-1)^2*p^(4e-3)*(p+1) - Dan Fux (danfux
@my-deja.com), Apr 18 2001
%Y A000252 The number of 2 X 2 matrices mod n with determinant 1 is A000056. The
 order of GL(2,K) for a finite field K is in sequence A059238.
%K A000252 nonn,easy,nice,mult
%O A000252 1,2
%A A000252 njas

------------------------------------------------------------------------
Another example of a multiplicative EIS sequence that could be improved
is A000056.  Here we have

%F A000056 Multiplicative with a(p^e) = (p-1)*p^(3e-2)*(p+1)

This sequence has Maple and Mma programs which are easy enough to derive
given the multiplicative nature of the sequence.  I assume Maple and Mma
provide primitives for multiplicative sequences; I would be tempted to
replace the existing programs with ones based on this primitive.

------------------------------------------------------------------------
I am thinking of downloading the EIS and trying to identify multiplicative
sequences and clean them up a bit.