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

N. J. A. Sloane njas at research.att.com
Wed Nov 26 04:38:24 CET 2008

Hugo,  We had a power failure on Sat which has caused a huge mess.

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?

ME:  I'll take 1000 terms , or 10000 if you feel that is warranted.
Or stop at the end of some convenient row.
Send it as an attachemnt.  (Not a zip file though)
how to send a b-file, by the way

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.

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

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;
ME: IN FACT it is A018805

(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

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

(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

ME: HERE'S your sequence with its A-number as it will appear in the OEIS:

%I A135646
%S A135646 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 A135646 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 A135646 11 15 20 22 26 23 26 22 20 15 11 12 17 22 25 29 29 29 29 25 22 17 12
%N A135646 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 A135646 a(n, n) = 2 \sum_1^n{ \phi(i) } - 1 = 2 A002088(n) - 1
%C A135646 a(m, n) <= mn - \sum_1^m{ (i - \phi(i)) floor(n / i) }
%e A135646 a(2, 5) = 8 since of the 10 possible pairs all but (2, 2) and (2, 4) are coprime
%Y A135646 Cf. A000010 (Euler's totient function), A002088 (sum of totient function)
%K A135646 nonn,tabl
%O A135646 1, 2
%A A135646 Hugo van der Sanden (hv at crypt.org), Nov 22 2008

NEIL