A064608 Partial sums of A034444: sum of number of unitary divisors from 1 to n.

1, 3, 5, 7, 9, 13, 15, 17, 19, 23, 25, 29, 31, 35, 39, 41, 43, 47, 49, 53, 57, 61, 63, 67, 69, 73, 75, 79, 81, 89, 91, 93, 97, 101, 105, 109, 111, 115, 119, 123, 125, 133, 135, 139, 143, 147, 149, 153, 155, 159, 163, 167, 169, 173, 177, 181, 185, 189, 191, 199, 201

Offset: 1

Author

Labos Elemer, Sep 24 2001

Keywords

• nonn
• easy

Comments

a(n) = Sum_{k<=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

• E. 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.
• E. Cohen, The number of unitary divisors of an integer, Am. Math. Mon. 67, 879-880 (1960).
• E. Landau, Handbuch der Lehre von der Verteilung der Primzahlen, vol. 2, Leipzig, Berlin, B. G. Teubner, 1909.
• E. Landau, Handbuch der Lehre von der Verteilung der Primzahlen, vol. 1 and vol. 2, Leipzig, Berlin, B. G. Teubner, 1909.
• F. Mertens, Uber einige asymptotische Gesetze der Zahlentheorie, J. Reine Angew. Math., 77 (1874), 289-338.
• 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.
• D. Zhang and W. Zhai, Mean Values of a Gcd-Sum Function Over Regular Integers Modulo n, J. Int. Seq. 13 (2010), 10.4.7. Eq (8) for asymptotics.

Crossrefs

Cf. A001620, A001221, A034444, A064610, A069212.

Programs

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 *)

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<Chai Wah Wu, Sep 07 2023

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