[seqfan] Re: Intermediate result for ordering problem: 2-D \phi()

[hv at crypt.org]

DW> Let p1 < p2 < ... < p_n be primes (call p1 = p, p2 = q, p3 = r, ...)
DW> Consider the set M of divisors of p1*p2*...*p_n. How many ways can M be
DW> ordered?
DW> For n = 0, we have m = { 1 }, with 1 ordering.
DW> For n = 1, we have M = { 1, p }. There is 1 possible ordering, 1 < p.
DW> For n = 2, we have M = { 1, p, q, pq }. Remembering p < q, there is again 1
DW> possible ordering, 1 < p < q < pq.
DW> For n = 3, we have M = { 1, p, q, r, pq, pr, qr, pqr }. There are 2 possible
DW> orderings here
DW> 1 < p < q < r < pq < pr < qr < pqr
DW> 1 < p < q < pq < r < pr < qr < pqr
DW> How many possible orderings are there for larger n?

HV> I've spent some time investigating a slightly more general case (where
HV> primes aren't restricted to appearing only once), which has posed some
HV> interesting computational challenges. I'm nearly done with that, and
HV> plan to write up the results soon.

NJAS> WHAT about the answer to David's original question - is that 
NJAS> sequence in the OEIS?  If not please send it!
NJAS> ALSO what about the more general version, same question!

As I mentioned in the previous paragraph, I'm coming to that. I'll try to
write up what I have this weekend. The actual values I have for the original
question are: 1, 1, 1, 2, 14, 516, 124187 (starting from n=0).

HV> In the meantime, that investigation led me to this sequence:
HV> a(m, n) is the number of pairs (i, j), 1 <= i <= m, 1 <= j <= n, such that (i, j) are coprime.
HV> .. a kind of 2-dimensional variant of \phi(n) which seems interesting enough
HV> to record in its own right.
HV> A couple of observations:
HV> 
HV> (1)   a(n, n) = 2 \sum_1^n{ \phi(i) } - 1
HV> .. which is nice, but probably not unique enough to warrant a separate OEIS entry;

NJAS> IN FACT it is A018805

Ah, missed that. I see you added a crossreference on the new sequence,
please add one on A018805 as well, and the formula A18805 = 2 A2088(n) - 1.

HV> (2)   a(m, n) <= mn - \sum_1^m{ (i - \phi(i)) floor(n / i) }
HV> 
HV> (3)   a(m, n) => mn - \sum_1^m{ (i - \phi(i))      (n / i) }  ???
HV>                  = n \sum_1^m{ \phi(i) / i }
HV>                  => 6mn / \pi^2  as m => \inf

NJAS> To me => means "implies" and >= means "greater than or equal to".
NJAS> I guess you meant the latter?

Sorry, I meant "tends to": the function is strictly no greater than (2)
with floor(), but I conjecture it is close to (3) where the floor() is
removed, and will tend to converge on that as m tends to infinity (in
fact as either m or n do), and as m tends to infinity that further
simplifies to 6mn/pi^2. Should I have used the symbol "->" instead?

[...]
NJAS> HERE'S your sequence with its A-number as it will appear in the OEIS:

Thanks, I'll sort out the b-file this weekend.

Hugo