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

[hv at crypt.org]

Neil: 1) please see sequence below; 2) I can provide more values as a b-file,
how would you like that submitted, and how many values are useful?

Back in August, David Wilson introduced an interesting problem:

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

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

In the meantime, that investigation led me to this sequence:

a(m, n) is the number of pairs (i, j), 1 <= i <= m, 1 <= j <= n, such
that (i, j) are coprime.

.. a kind of 2-dimensional variant of \phi(n) which seems interesting enough
to record in its own right.

A couple of observations:

(1)   a(n, n) = 2 \sum_1^n{ \phi(i) } - 1
.. which is nice, but probably not unique enough to warrant a separate
OEIS entry;

(2)   a(m, n) <= mn - \sum_1^m{ (i - \phi(i)) floor(n / i) }

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

(3) is pure conjecture - while I expect the contribution for each i to be
close to this value, I have no proof that the discrepancies will tend to
cancel out as m increases, so the result could be quite different asymptotic
behaviour. I'd be interested if anyone can get some firmer results.

The results below parse as:
1 - a(1, 1)
2 2 - a(2, 1), a(1, 2)
3 3 3 - a(3, 1), a(2, 2), a(1, 3), etc
4 5 5 4
5 6 7 6 5
6 8 9 9 8 6
7 9 12 11 12 9 7
8 11 13 15 15 13 11 8
9 12 16 16 19 16 16 12 9
10 14 18 20 21 21 20 18 14 10
etc

%I A000001
%S A000001 1 2 2 3 3 3 4 5 5 4 5 6 7 6 5 6 8 9 9 8 6 7 9 12 11 12 9 7 8 11 13
%T A000001 15 15 13 11 8 9 12 16 16 19 16 16 12 9 10 14 18 20 21 21 20 18 14 10
%U A000001 11 15 20 22 26 23 26 22 20 15 11 12 17 22 25 29 29 29 29 25 22 17 12
%N A000001 a(m, n) is the number of coprime pairs (i, j) with 1 <= i <= m, 1 <= j <= n; table of a(m, n) read by antidiagonals.
%C A000001 a(n, n) = 2 \sum_1^n{ \phi(i) } - 1 = 2 A002088(n) - 1
%C A000001 a(m, n) <= mn - \sum_1^m{ (i - \phi(i)) floor(n / i) }
%e A000001 a(2, 5) = 8 since of the 10 possible pairs all but (2, 2) and (2, 4) are coprime
%Y A000001 Cf. A000010 (Euler's totient function), A002088 (sum of totient function)
%K A000001 nonn,tabl
%O A000001 1, 2
%A A000001 Hugo van der Sanden (hv at crypt.org), Nov 22 2008

Hugo