[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