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. - 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) is the number of rational numbers which can be constructed from the set of integers between 1 and n, without combination of multiplication and division. a(3) = 7 because {1, 2, 3} can only create {1/3, 1/2, 2/3, 1, 3/2, 2, 3}. - Bernard Schott, Jul 07 2019
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. See Theorem 332.
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.
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence)
Eric Weisstein's World of Mathematics, Carefree Couple
FORMULA
a(n) = 2*(Sum_{j=1..n} phi(j)) - 1.
a(n) = n^2 - Sum_{j=2..n} a(floor(n/j)).
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) ~ 6*n^2/Pi^2 + O(n*log n). - N. J. A. Sloane, May 31 2020
a(n) = Sum_{k=1..n} mu(k)*floor(n/k)^2. - Benoit Cloitre, May 11 2003
a(n) = A242114(floor(n/k),1), 1<=k<=n; particularly a(n) = A242114(n,1). - Reinhard Zumkeller, May 04 2014
a(n) = 2 * A005728(n) - 3. - David H Post, Dec 20 2016
a(n) ~ 6*n^2/Pi^2, cf. A059956. [Hardy and Wright] - M. F. Hasler, Jan 20 2017
G.f.: (1/(1 - x)) * (-x + 2 * Sum_{k>=1} mu(k) * x^k / (1 - x^k)^2). - Ilya Gutkovskiy, Feb 14 2020
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 */
(PARI) a(n)=my(s); forsquarefree(k=1, n, s+=moebius(k)*(n\k[1])^2); s \\ Charles R Greathouse IV, Jan 08 2018
(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
(Python)
from sympy import sieve
def A018805(n): return 2*sum(t for t in sieve.totientrange(1, n+1)) - 1 # Chai Wah Wu, Mar 23 2021
(Python)
from functools import lru_cache
@lru_cache(maxsize=None)
def A018805(n): # based on second formula
if n == 0:
return 0
c, j = 1, 2
k1 = n//j
while k1 > 1:
j2 = n//k1 + 1
c += (j2-j)*A018805(k1)
j, k1 = j2, n//j2
return n*(n-1)-c+j # Chai Wah Wu, Mar 24 2021
CROSSREFS
KEYWORD
nonn,nice
AUTHOR
EXTENSIONS
More terms from Reinhard Zumkeller, Apr 08 2006
Link to Moree's paper corrected by Peter Luschny, Aug 08 2009
STATUS
approved