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

[David Wilson]

    a(m, n)  =  mn - SUM(2 <= k <= min(m, n), a([m/k], [n/k])).

If you use this recurrence and cache results, you can compute a(m, n) in 
O(sqrt(max(m, n))) additions.

The special case

    a(n, n) = a(n) = n^2 - SUM(2 <= k <= n, a([n/k]))

is a formula for A018805 already included in that sequence (just not in 
a conspicuous place).

The formula naturally generalizes to higher dimension, e.g,

    a(m, n, p) = mnp - SUM(2 <= k <= min(m, n, p), a([m/k], [n/k], [p/k]))

counts triples in [1..m] x [1..n] x [1..p] with gcd 1.
> 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
>