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

 

Logo

Annual Appeal: Today, Nov 11 2014, is the 4th anniversary of the launch of the new OEIS web site. 70,000 sequences have been added in these four years, all edited by volunteers. Please make a donation (tax deductible in the US) to help keep the OEIS running.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A018805 Number of elements in the set {(x,y): 1<=x,y<=n, gcd(x,y)=1}. 43
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

a(n) = A242114(floor(n/k),1), 1<=k<=n; particularly a(n)=A242114(n,1). - Reinhard Zumkeller, May 04 2014

REFERENCES

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 Gérard, Table of n, a(n) for n = 1..100000 [Replaces an earlier b-file from Charles R Greathouse IV]

Jin-Yi Cai and Eric Bach, 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).

Pieter Moree, Counting carefree couples, arXiv:math/0510003 [math.NT], 2005-2014.

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

MAPLE

N:= 1000; # to get the first N entries

P:= Array(1..N, numtheory:-phi);

A:= map(t -> 2*round(t)-1, Statistics:-CumulativeSum(P));

convert(A, list); # Robert Israel, Jul 16 2014

MATHEMATICA

FoldList[ Plus, 1, 2 Array[ EulerPhi, 60, 2 ] ] (* Olivier Gérard, Aug 15 1997 *)

Accumulate[2*EulerPhi[Range[60]]]-1 (* Harvey P. Dale, Oct 21 2013 *)

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.

Cf. A177853 (partial sums).

Sequence in context: A092109 A117991 A118260 * A191037 A135932 A231847

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

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

Content is available under The OEIS End-User License Agreement .

Last modified November 23 07:56 EST 2014. Contains 249839 sequences.