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

Author

Hugo van der Sanden, Nov 22 2008

Keywords

• nonn
• tabl

Comments

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

Examples

			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.
		

Links

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

Crossrefs

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

Cf. A049687.

Programs

PARI

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

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