login
This site is supported by donations to The OEIS Foundation.

 

Logo


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 * A101646 A166079 A269381

Adjacent sequences:  A135643 A135644 A135645 * A135647 A135648 A135649

KEYWORD

nonn,tabl,changed

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified September 25 18:20 EDT 2017. Contains 292499 sequences.