[seqfan] Re: Multiplicative sequences

[franktaw at netscape.net]

I'm inclined to think that you have the right definition, at least for 
the primary sequence(s).  If you allow a(k) = 0, then you have to ask 
whether you allow the all-zeros sequence, or still require a(1) = 1.  
(Note that a(1) = 0 is the only other possibility; since gcd(1,1) = 1, 
a(1) = a(1)^2.)  The definition you're using avoids all that.  The fact 
that there aren't further complications to decide about is a strong 
indicator that this is the right one.  (Which is not to say that one or 
more of the others might not be added later.)  On the other hand, there 
is no reason to exclude m = 1 or n = 1.

I don't really have any suggestions for efficient calculation.

The number of multiplicative sequences b with b(k) <= k for all k can 
also be counted.  In this case, we have a(1) = 1; if n is a prime 
power, a(n) = n*a(n-1), and otherwise a(n) = a(n-1).  This starts:

1, 2, 6, 24, 120, 120, 840, 6720, 60480, 60480, 665280, 665280, 
8648640, 8648640, 8648640, 138378240, 2352430080, 2352430080, 
44696171520, 44696171520

which is not in the OEIS, although the unique terms are in A024923.

Franklin T. Adams-Watters

-----Original Message-----
From: Charles Greathouse <charles.greathouse at case.edu>

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


_______________________________________________

Seqfan Mailing list - http://list.seqfan.eu/