OFFSET
1,2
COMMENTS
a(n) = Sum_{k=1..n} 2^omega(k) where omega(k) is the number of distinct primes in the factorization of k. - Benoit Cloitre, Apr 16 2002
a(n) is the number of (p, q) lattice points that are visible from (0, 0), where p and q satisfy: p >= 1, q >= 1, p * q <= n. - Luc Rousseau, Jul 09 2017
REFERENCES
Edmund Landau, Handbuch der Lehre von der Verteilung der Primzahlen, Leipzig 1909 (Chelsea reprint 1953), p. 594.
LINKS
Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from Harry J. Smith)
Masum Billal, Number of Ways To Write as Product of Co-prime Numbers, arXiv:1909.07823 [math.GM], 2019-2021.
Eckford Cohen, The number of unitary divisors of an integer, The American Mathematical Monthly, Vol. 67, No. 9 (1960), pp. 879-880.
Edmund Landau, Handbuch der Lehre von der Verteilung der Primzahlen, vol. 2, Leipzig, Berlin, B. G. Teubner, 1909.
Edmund Landau, Handbuch der Lehre von der Verteilung der Primzahlen, vol. 1 and vol. 2, Leipzig, Berlin, B. G. Teubner, 1909.
Franz Mertens, Uber einige asymptotische Gesetze der Zahlentheorie, J. Reine Angew. Math., 77 (1874), 289-338.
Mehtaab Sawhney, Problem H-807, Advanced Problems and Solutions, The Fibonacci Quarterly, Vol. 55, No. 2 (2017), p. 184; Identities with sums of Euler and number of squarefree divisors functions, Solution to Problem H-807 by the proposer, ibid., Vol. 57, No. 2 (2019), pp. 186-187.
V. Sitaramaiah and M.V. Subbarao, Unitary divisor problem for arithmetic progressions, Annales Univ. Sci. Budapest., Sect. Comp. 32 (2010), 73-89.
D. Suryanarayana and V. Siva Rama Prasad, The number of k-free divisors of an integer, Acta Arithmetica XVII (1971), 345-354.
Deyu Zhang and Wenguang Zhai, Mean Values of a Gcd-Sum Function Over Regular Integers Modulo n, J. Int. Seq. 13 (2010), Article 10.4.7. Eq (8) for asymptotics.
FORMULA
a(n) = a(n-1) + A034444(n) = a(n-1) + 2^A001221(n) Sum_{j=1..n} ud(j) where ud(j) = A034444(j) = 2^A001221(n).
a(n) = n*log(n)/zeta(2) + O(n) where zeta(2) = Pi^2/6. - Benoit Cloitre, Apr 16 2002
a(n) = Sum_{k=1..n} mu(k)^2*floor(n/k). - Benoit Cloitre, Apr 16 2002
Mertens's theorem (1874): a(n) = Sum_{k<=n} ud(k) = (n/zeta(2))*(log(n) + 2*gamma - 1 - 2*zeta'(2)/zeta(2)) + O(sqrt(n)*log(n)), where gamma is the Euler-Mascheroni constant A001620. - Antonio G. Astudillo (afg_astudillo(AT)hotmail.com), Sep 07 2002
G.f.: (1/(1 - x))*Sum_{k>=1} mu(k)^2*x^k/(1 - x^k). - Ilya Gutkovskiy, Jan 03 2017
a(n) = Sum_{i=1..n} Sum_{j=1..n} mu(gcd(i, j)) * floor(sqrt(n/(i*j))), where mu is the Moebius function (A008683) (Sawhney, 2017). - Amiram Eldar, Dec 29 2025
MAPLE
with(numtheory): A064608:=n->add(mobius(k)^2*floor(n/k), k=1..n): seq(A064608(n), n=1..100); # Wesley Ivan Hurt, Dec 05 2015
MATHEMATICA
a[n_] := Count[Divisors@ n, d_ /; GCD[d, n/d] == 1]; Accumulate@ Array[a, {61}] (* Michael De Vlieger, Oct 21 2015, after Jean-François Alcover at A034444 *)
Accumulate@ Array[2^PrimeNu[#] &, {61}] (* Amiram Eldar, Oct 21 2019 *)
PROG
(PARI) { for (n=1, 80, a=sum(k=1, n, moebius(k)^2*floor(n/k)); write("b064608.txt", n, " ", a) ) } \\ Harry J. Smith, Sep 20 2009
(PARI) a(n)=sum(k=1, sqrtint(n), moebius(k)*(2*sum(l=1, sqrtint(n\(k*k)), n\(k*k*l))-sqrtint(n\(k*k))^2)); \\ More efficient formula for large n values (up to 10^14)
vector(80, i, a(i)) \\ Jerome Raulin, Nov 01 2015
(Python)
from sympy.ntheory.factor_ import primenu
def A064608(n): return sum(1<<primenu(m) for m in range(1, n+1)) # Chai Wah Wu, Sep 07 2023
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Labos Elemer, Sep 24 2001
STATUS
approved