|
| |
|
|
A018805
|
|
Number of elements in the set {(x,y): 1<=x,y<=n, gcd(x,y)=1}.
|
|
41
|
|
|
|
1, 3, 7, 11, 19, 23, 35, 43, 55, 63, 83, 91, 115, 127, 143, 159, 191, 203, 239, 255, 279, 299, 343, 359, 399, 423, 459, 483, 539, 555, 615, 647, 687, 719, 767, 791, 863, 899, 947, 979, 1059, 1083, 1167, 1207, 1255, 1299, 1391, 1423, 1507, 1547, 1611, 1659, 1763
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
Number of positive rational numbers of height at most n, where the height of p/q is max(p, q) when p and q are relatively prime positive integers. - Charles R Greathouse IV, Jul 05 2012
The number of ordered pairs (i,j) with 1<=i<=n, 1<=j<=n, gcd(i,j)=d} is a(floor(n/d)). - N. J. A. Sloane, Jul 29 2012
Equals partial sums of A140434 (1, 2, 4, 4, 8, 4, 12, 8,...) and row sums of triangle A143469. [From Gary W. Adamson, Aug 17 2008]
Number of distinct solutions to k*x+h=0, where 1 <= k,h <= n. - Giovanni Resta, Jan 08 2013
a(n) = A000290(n) - A100613(n) = A015614(n) + A002088(n). - Reinhard Zumkeller, Jan 21 2013
|
|
|
REFERENCES
|
Cai, Jin-Yi and Bach, Eric. On testing for zero polynomials by a set of points with bounded precision, Theoret. Comput. Sci. 296 (2003), no. 1, 15-25. MR1965515 (2004m:68279).
S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 110-112.
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 3rd ed., Oxford Univ. Press, 1954.
|
|
|
LINKS
|
Olivier GERARD, Table of n, a(n) for n = 1..100000 [Replaces an earlier b-file from Charles R Greathouse IV]
Pieter Moree, Counting carefree couples
Eric Weisstein's World of Mathematics, Carefree Couple
|
|
|
FORMULA
|
a(n) = 2*( Sum phi(j), j=1..n ) - 1.
a(n) = n^2 - Sum a([ n/j ]), j=2..n.
a(n) = 2*A015614(n) + 1. - Reinhard Zumkeller, Apr 08 2006
a(n) = 2*A002088(n) - 1. - Hugo van der Sanden, Nov 22 2008
a(n) ~ (1/Zeta(2)) * n^2 = (6/pi^2) * n^2 as n goes to infinity (zeta is the Riemann zeta function, A013661, and the constant 6/pi^2 is 0.607927..., A059956). - Ahmed Fares (ahmedfares(AT)my-deja.com), Jul 18 2001
a(n) = sum(k=1, n, mu(k)*floor(n/k)^2). - Benoit Cloitre, May 11 2003
|
|
|
MATHEMATICA
|
FoldList[ Plus, 1, 2 Array[ EulerPhi, 60, 2 ] ] (* Olivier Gerard, Aug 15 1997 *)
|
|
|
PROG
|
(PARI) a(n)=sum(k=1, n, moebius(k)*(n\k)^2)
(PARI)
A018805(n)=2 *sum(j=1, n, eulerphi(j)) - 1;
for(n=1, 99, print1(A018805(n), ", ")); /* show terms */
(MAGMA) /* based on the first formula */ A018805:=func< n | 2*&+[ EulerPhi(k): k in [1..n] ]-1 >; [ A018805(n): n in [1..60] ]; // Klaus Brockhaus, Jan 27 2011
(MAGMA) /* based on the second formula */ A018805:=func< n | n eq 1 select 1 else n^2-&+[ $$(n div j): j in [2..n] ] >; [ A018805(n): n in [1..60] ]; // Klaus Brockhaus, Feb 07 2011
(Haskell)
a018805 n = length [()| x <- [1..n], y <- [1..n], gcd x y == 1]
-- Reinhard Zumkeller, Jan 21 2013
|
|
|
CROSSREFS
|
Cf. A015614, A002088, A100613 (gcd > 1), A071778 (triples), A143469, A140434, A013661, A059956, A137243, A171503.
Sequence in context: A092109 A117991 A118260 * A191037 A135932 A105876
Adjacent sequences: A018802 A018803 A018804 * A018806 A018807 A018808
|
|
|
KEYWORD
|
nonn,nice
|
|
|
AUTHOR
|
David W. Wilson
|
|
|
EXTENSIONS
|
More terms from Reinhard Zumkeller, Apr 08 2006
Link to Moree's paper corrected Peter Luschny, Aug 08 2009
|
|
|
STATUS
|
approved
|
| |
|
|
