cp's OEIS Frontend

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.

%I A135646 #11 Sep 18 2017 03:09:32
%S A135646 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,
%T A135646 15,15,13,11,8,9,12,16,16,19,16,16,12,9,10,14,18,20,21,21,20,18,14,10,
%U A135646 11,15,20,22,26,23,26,22,20,15,11,12,17,22,25,29,29,29,29,25,22,17,12
%N 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.
%C A135646 A kind of 2-dimensional version of the Euler phi function A000010.
%H A135646 Andrew Howroyd, <a href="/A135646/b135646.txt">Table of n, a(n) for n = 1..1275</a>
%F A135646 a(m, n) = Sum_{g=1..min(m,n)} floor(m/g) * floor(n/g) * moebius(g). - _Andrew Howroyd_, Sep 17 2017
%F A135646 a(n, n) = 2*(Sum_{i=1..n} phi(i)) - 1 = 2*A002088(n) - 1 = A018805(n).
%F A135646 a(m, n) <= m*n - Sum_{i=1..m} ( (i - phi(i)) * floor(n / i) ).
%F A135646 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.
%F A135646 a(m, n) = A049687(m, n) + 2. - _Andrew Howroyd_, Sep 17 2017
%e A135646 a(2, 5) = 8 since of the 10 possible pairs all but (2, 2) and (2, 4) are coprime.
%e A135646 The terms given correspond to the following values:
%e A135646    1 = a(1, 1)
%e A135646    2  2 = a(2, 1), a(1, 2)
%e A135646    3  3  3 = a(3, 1), a(2, 2), a(1, 3), etc.
%e A135646    4  5  5  4
%e A135646    5  6  7  6  5
%e A135646    6  8  9  9  8  6
%e A135646    7  9 12 11 12  9  7
%e A135646    8 11 13 15 15 13 11  8
%e A135646    9 12 16 16 19 16 16 12  9
%e A135646   10 14 18 20 21 21 20 18 14 10
%e A135646   etc.
%o A135646 (PARI) a(m,n) = sum(g=1, min(m,n), (m\g)*(n\g)*moebius(g)); \\ _Andrew Howroyd_, Sep 17 2017
%Y A135646 Cf. A000010 (Euler's totient function), A002088 (sum of totient function), A018805.
%Y A135646 Cf. A049687.
%K A135646 nonn,tabl
%O A135646 1,2
%A A135646 _Hugo van der Sanden_, Nov 22 2008