# [seqfan] Multiplicative sequences

Charles Greathouse charles.greathouse at case.edu
Wed Mar 3 05:01:59 CET 2010

```Following Tim Gowers's search
http://gowers.wordpress.com/
for a solution to the Erdős discrepancy problem, I have recently been
thinking about the number of multiplicative sequences.  Now the
natural sequence where a(n) is the number of multiplicative sequences
increases too fast for the OEIS (to wit: 1, infinity, ...) so I was
thinking of the two place function where f(m, n) is the number of
multiplicative sequences of length m using only 1, 2, ..., n.

There are several issues to be addressed in turning this into a
sequence, of course: what offsets, which order of variables, are the
trivial rows/columns with m = 1 or n = 1 allowed, are length 1
sequences constrained to be 1, and whether 0..n is more natural than
1..n.  I bring that here for suggestions, along with the harder issues
of calculation (naively, about n^(m/log m) steps are needed) and
referencing.  Good asymptotic results, or bounds better than the
trivial
f(m, n+1) > f(m, n)
f(m + 1, n) = nf(m, n) if m+1 is a prime power
f(m + 1, n) < f(m, n) otherwise
etc. would also be welcome.

Of course if an equivalent sequence is already in the database and I
have simply missed it, I would be pleased to hear about that as well.

f(m, 2) is 1, 2, 4, 8, 16, 12, 24, 48, 96, 80, 160, ...
f(m, 3) is 1, 3, 9, 27, 81, 45, 135, 405, 1215, 891, 2673, ...
f(m, 4) is 1, 4, 16, 64, 256, 128, 512, 2048, 8192, 5632, ...
The antidiagonals are 1; 1,1; 1,2,1; 1,4,3,1; 1,8,9,4,1;
1,16,27,16,5,1; 1,12,81,64,25,6,1; ...

Charles Greathouse
Analyst/Programmer
Case Western Reserve University

```