[seqfan] Re: Intermediate result for ordering problem: 2-D \phi()
hv at crypt.org
hv at crypt.org
Sun Nov 30 09:13:50 CET 2008
That's very nice. Though it makes the computation less obvious, I'd rather
express it as:
mn = sum_{k=1}^\inf { a([m/k], [n/k]) }
.. in which each component of the sum counts the pairs with gcd equal to k
(and analogously for higher dimension).
Hugo
David Wilson <dwilson at gambitcomm.com> wrote:
:
:
: 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