login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

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 56th year, we are closing in on 350,000 sequences, and we’ve crossed 9,700 citations (which often say “discovered thanks to the OEIS”).

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 2
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 (list; table; graph; refs; listen; history; text; internal format)
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: A124882 A262518 A085578 * A334922 A301851 A101646

Adjacent sequences:  A135643 A135644 A135645 * A135647 A135648 A135649

KEYWORD

nonn,tabl

AUTHOR

Hugo van der Sanden, Nov 22 2008

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 4 02:40 EST 2021. Contains 349469 sequences. (Running on oeis4.)