[seqfan] Re: Intermediate result for ordering problem: 2-D \phi()
David Wilson
dwilson at gambitcomm.com
Wed Nov 26 22:02:11 CET 2008
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
>
More information about the SeqFan
mailing list