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.

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, 15, 15, 13, 11, 8, 9, 12, 16, 16, 19, 16, 16, 12, 9, 10, 14, 18, 20, 21, 21, 20, 18, 14, 10, 11, 15, 20, 22, 26, 23, 26, 22, 20, 15, 11, 12, 17, 22, 25, 29, 29, 29, 29, 25, 22, 17, 12

Offset

1,2

Comments

A kind of 2-dimensional version of the Euler phi function A000010.

Links

Andrew Howroyd, Table of n, a(n) for n = 1..1275

Formula

a(m, n) = Sum_{g=1..min(m,n)} floor(m/g) * floor(n/g) * moebius(g). - Andrew Howroyd, Sep 17 2017

a(n, n) = 2*(Sum_{i=1..n} phi(i)) - 1 = 2*A002088(n) - 1 = A018805(n).

a(m, n) <= m*n - Sum_{i=1..m} ( (i - phi(i)) * floor(n / i) ).

Conjecture: a(m, n) ~ mn - sum_1^m{ (i - phi(i)) (n / i) } = n sum_1^m{ phi(i) / i } ~ 6mn / pi^2 as m -> oo.

a(m, n) = A049687(m, n) + 2. - Andrew Howroyd, Sep 17 2017

Example

a(2, 5) = 8 since of the 10 possible pairs all but (2, 2) and (2, 4) are coprime.
The terms given correspond to the following values:
   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.

Prog

(PARI) a(m, n) = sum(g=1, min(m, n), (m\g)*(n\g)*moebius(g)); \\ Andrew Howroyd, Sep 17 2017

Crossrefs

Cf. A000010 (Euler's totient function), A002088 (sum of totient function), A018805.

Cf. A049687.

Sequence in context: A085578 A350066 A360917 * A360920 A334922 A301851

Adjacent sequences: A135643 A135644 A135645 * A135647 A135648 A135649

Keyword

nonn,tabl

Author

Hugo van der Sanden, Nov 22 2008

Status

approved