login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

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.
2

%I #11 Sep 18 2017 03:09:32

%S 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 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 11,15,20,22,26,23,26,22,20,15,11,12,17,22,25,29,29,29,29,25,22,17,12

%N 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 A kind of 2-dimensional version of the Euler phi function A000010.

%H Andrew Howroyd, <a href="/A135646/b135646.txt">Table of n, a(n) for n = 1..1275</a>

%F a(m, n) = Sum_{g=1..min(m,n)} floor(m/g) * floor(n/g) * moebius(g). - _Andrew Howroyd_, Sep 17 2017

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

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

%F 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 a(m, n) = A049687(m, n) + 2. - _Andrew Howroyd_, Sep 17 2017

%e a(2, 5) = 8 since of the 10 possible pairs all but (2, 2) and (2, 4) are coprime.

%e The terms given correspond to the following values:

%e 1 = a(1, 1)

%e 2 2 = a(2, 1), a(1, 2)

%e 3 3 3 = a(3, 1), a(2, 2), a(1, 3), etc.

%e 4 5 5 4

%e 5 6 7 6 5

%e 6 8 9 9 8 6

%e 7 9 12 11 12 9 7

%e 8 11 13 15 15 13 11 8

%e 9 12 16 16 19 16 16 12 9

%e 10 14 18 20 21 21 20 18 14 10

%e etc.

%o (PARI) a(m,n) = sum(g=1, min(m,n), (m\g)*(n\g)*moebius(g)); \\ _Andrew Howroyd_, Sep 17 2017

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

%Y Cf. A049687.

%K nonn,tabl

%O 1,2

%A _Hugo van der Sanden_, Nov 22 2008