A066779 -id:A066779 - cp's OEIS frontend

A013928 Number of (positive) squarefree numbers < n.

0, 1, 2, 3, 3, 4, 5, 6, 6, 6, 7, 8, 8, 9, 10, 11, 11, 12, 12, 13, 13, 14, 15, 16, 16, 16, 17, 17, 17, 18, 19, 20, 20, 21, 22, 23, 23, 24, 25, 26, 26, 27, 28, 29, 29, 29, 30, 31, 31, 31, 31, 32, 32, 33, 33, 34, 34, 35, 36, 37, 37, 38, 39, 39, 39, 40, 41, 42, 42, 43, 44, 45, 45, 46, 47, 47, 47, 48, 49, 50, 50, 50, 51

Offset: 1

Henri Lifchitz

For n >= 1 define an n X n (0, 1) matrix A by A[i, j] = 1 if gcd(i, j) = 1, A[i, j] = 0 if gcd(i, j) > 1 for 1 <= i,j <= n . The rank of A is a(n + 1). Asymptotic expression for a(n) is a(n) ~ n * 6 / Pi^2. - Sharon Sela (sharonsela(AT)hotmail.com), May 06 2002
a(n) = Sum_{k=1..n-1} A008966(k). - Reinhard Zumkeller, Jul 05 2010
For all n >= 1, a(n)/n >= a(176)/176 = 53/88, and the equality occurs only for n=176 (see K. Rogers link). - Michel Marcus, Dec 16 2012 [Thus the Schnirelmann density of the squarefree numbers is 53/88. - Charles R Greathouse IV, Feb 02 2016]
Cohen, Dress, & El Marraki prove that |a(n) - 6n/Pi^2| < 0.02767*sqrt(n) for n >= 438653. - Charles R Greathouse IV, Feb 02 2016

			a(10) = 6 because there are 6 squarefree numbers up to 10: 1, 2, 3, 5, 6, 7.
a(11) = 7 because there are 7 squarefree numbers up to 11: the numbers listed above for 10, plus 10 itself.
a(13) = 8 because the 12 X 12 matrix described in the first comment by Sharon Sela has rank 8. Rows 2,4,8 (the powers of two) are identical, rows 3,9 (the powers of three) are identical, and rows 6 and 12 (same prime factors) are identical. - _Geoffrey Critzer_, Dec 07 2014
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
1, 0, 1, 0, 1, 0, 1, 0, 1, 0  1, 0, ...
1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, ...
1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, ...
1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, ...
1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, ...
1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, ...
1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, ...
1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, ...
1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, ...
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, ...
1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, ...
.                                   .
.                                    .
.                                     .

G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Fifth edition (1979), Clarendon Press, pp. 269-270.
E. Landau, Über den Zusammenhang einiger neuer Sätze der analytischen Zahlentheorie, Wiener Sitzungberichte, Math. Klasse 115 (1906), pp. 589-632. Cited in Sándor, Mitrinović, & Crstici.
József Sándor, Dragoslav S. Mitrinovic, and Borislav Crstici, Handbook of Number Theory I. Springer, 2005. Section VI.18.

Daniel Forgues, Table of n, a(n) for n = 1..100000 (first 1000 terms from T. D. Noe)
Henri Cohen, Francois Dress, and Mahomed El Marraki, Explicit estimates for summatory functions linked to the Möbius μ-function, Funct. Approx. Comment. Math. 37:1 (2007), pp. 51-63.
G. H. Hardy and S. Ramanujan, The normal number of prime factors of a number n, Q. J. Math., 48 (1917), pp. 76-92.
L. Moser and R. A. MacLeod, The error term for the squarefree integers, Canad. Math. Bull. vol. 9, no. 3, (1966).
K. Rogers, The Schnirelmann density of the squarefree integers, Proc. Amer. Math. Soc. 15 (1964), pp. 515-516.
A. M. Vaidya, On the order of the error function of the square free numbers, Proc. Nat. Inst. Sci. India Part A 32 (1966), pp. 196-201.
Eric Weisstein's World of Mathematics, Squarefree.

One less than A107079.
Cf. A005117, A002321, A057627, A179211, A000720, A081239, A066779, A179215, A284584.
Cf. A158819 Number of squarefree numbers <= n minus round(n/zeta(2)).

a013928 n = a013928_list !! (n-1)
a013928_list = scanl (+) 0 $ map a008966 [1..]
-- Reinhard Zumkeller, Aug 03 2012

ListTools:-PartialSums([0,seq(numtheory:-mobius(i)^2,i=1..100)]); # Robert Israel, Dec 11 2014

Accumulate[Table[Abs[MoebiusMu[n]], {n, 0, 79}]] (* Alonso del Arte, Oct 07 2012 *)
Accumulate[Table[If[SquareFreeQ[n],1,0],{n,0,80}]] (* Harvey P. Dale, Mar 06 2019 *)

a(n)=sum(i=1,n-1,if(issquarefree(i),1,0)) \\ Lifchitz

a(n)=n--;sum(k=1,sqrtint(n),moebius(k)*(n\k^2)) \\ Benoit Cloitre, Oct 25 2009

a(n)=n--; my(s); forfactored(k=1,sqrtint(n), s += n\k[1]^2*moebius(k)); s \\ Charles R Greathouse IV, Nov 05 2017

a(n)=n--; my(s); forsquarefree(k=1, sqrtint(n), s += n\k[1]^2*moebius(k)); s \\ Charles R Greathouse IV, Jan 08 2018

from sympy.ntheory.factor_  import core
def a(n): return sum ([1 for i in range(1, n) if core(i) == i]) # Indranil Ghosh, Apr 16 2017

from math import isqrt
from sympy import mobius
def A013928(n): return sum(mobius(k)*((n-1)//k**2) for k in range(1,isqrt(n-1)+1)) # Chai Wah Wu, Jan 03 2024

a(n) = Sum_{k = 1..n-1} mu(k)^2. - Vladeta Jovovic, May 18 2001
a(n) = Sum_{d = 1..floor(sqrt(n - 1))} mu(d)*floor((n - 1)/d^2) where mu(d) is the Moebius function (A008683). - Vladeta Jovovic, Apr 06 2001
Asymptotic formula (with error term): a(n) = Sum_{k = 1..n-1} mu(k)^2 = Sum_{k = 1..n-1} |mu(k)| = 6*n/Pi^2 + O(sqrt(n)). - Antonio G. Astudillo (afg_astudillo(AT)hotmail.com), Jul 20 2002
a(n) = Sum_{k = 0..n} if(k <= n-1, mu(n - k) mod 2, else 0; a(n + 1) = Sum_{k = 0..n} mu(n - k + 1) mod 2. - Paul Barry, May 10 2005
a(n + 1) = Sum_{k = 0..n} abs(mu(n - k + 1)). - Paul Barry, Jul 20 2005
a(n) = Sum_{k = 1..floor(sqrt(n))} mu(k)*floor(n/k^2). - Benoit Cloitre, Oct 25 2009
Landau proved that a(n) = 6*n/Pi^2 + o(sqrt(n)). - Charles R Greathouse IV, Feb 02 2016
Vaidya proved that a(n) = 6*n/Pi^2 + O(n^k) for any k > 2/5 on the Riemann hypothesis. - Charles R Greathouse IV, Feb 02 2016
a(n) = A107079(n)-1. - Antti Karttunen, Oct 07 2016
G.f.: Sum_{k>=1} mu(k)^2*x^(k+1)/(1 - x). - Ilya Gutkovskiy, Feb 06 2017
a(n+1) = n - A057627(n) - Antti Karttunen, Apr 17 2017

A034387 Sum of primes <= n.

Original entry on oeis.org

0, 2, 5, 5, 10, 10, 17, 17, 17, 17, 28, 28, 41, 41, 41, 41, 58, 58, 77, 77, 77, 77, 100, 100, 100, 100, 100, 100, 129, 129, 160, 160, 160, 160, 160, 160, 197, 197, 197, 197, 238, 238, 281, 281, 281, 281, 328, 328, 328, 328, 328, 328, 381, 381, 381, 381, 381

Offset: 1

N. J. A. Sloane

Also sum of all prime factors in n!.
For large n, these numbers can be closely approximated by the number of primes < n^2. For example, the sum of primes < 10^10 = 2220822432581729238. The number of primes < (10^10)^2 or 10^20 = 2220819602560918840. This has a relative error of 0.0000012743... - Cino Hilliard, Jun 08 2008
Equals row sums of triangle A143537. - Gary W. Adamson, Aug 23 2008
Partial sums of A061397. - Reinhard Zumkeller, Mar 21 2014

T. D. Noe, Table of n, a(n) for n = 1..10000
Jens Askgaard, On the additive period length of the Sprague-Grundy function of certain Nim-like games, arXiv:1902.06299 [math.CO], 2019. See p. 25.
Cino Hilliard, Sum of primes
Matt Visser, On the arithmetic average of the first n primes, arXiv:2505.04951 [math.NT], 2025. See p. 3.

Cf. A007504, A158662, A073837, A066779, A034386, A000720.

This is a lower bound on A287881.

a034387 n = a034387_list !! (n-1)
a034387_list = scanl1 (+) a061397_list
-- Reinhard Zumkeller, Mar 21 2014

a:= proc(n) option remember; `if`(n<1, 0,
      a(n-1)+`if`(isprime(n), n, 0))
    end:
seq(a(n), n=1..60);  # Alois P. Heinz, Jun 29 2022

s=0; Table[s=s+n*Boole[PrimeQ[n]],{n,100}] (* Zak Seidov, Apr 11 2011 *)
Accumulate[Table[If[PrimeQ[n],n,0],{n,60}]] (* Harvey P. Dale, Jul 25 2016 *)

a(n)=sum(i=1,primepi(n),prime(i)) \\ Michael B. Porter, Sep 22 2009

a=0;for(k=1,100,print1(a=a+k*isprime(k),", ")) \\ Zak Seidov, Apr 11 2011

a(n) = if(n <= 1, return(0)); my(r=sqrtint(n)); my(V=vector(r, k, n\k)); my(L=n\r-1); V=concat(V, vector(L, k, L-k+1)); my(T=vector(#V, k, V[k]*(V[k]+1)\2)); my(S=Map(matrix(#V,2,x,y,if(y==1,V[x],T[x])))); forprime(p=2, r, my(sp=mapget(S,p-1), p2=p*p); for(k=1, #V, if(V[k] < p2, break); mapput(S, V[k], mapget(S,V[k]) - p*(mapget(S,V[k]\p) - sp)))); mapget(S,n)-1; \\ Daniel Suteu, Jun 29 2022

from sympy import isprime
from itertools import accumulate
def alist(n): return list(accumulate(k*isprime(k) for k in range(1, n+1)))
print(alist(57)) # Michael S. Branicky, Sep 18 2021

From the prime number theorem a(n) has the asymptotic expression: a(n) ~ n^2 / (2 log n). - Dan Fux (dan.fux(AT)OpenGaia.com), Apr 07 2001
a(n) = A158662(n) - 1. a(p) - a(p-1) = p, for p = primes (A000040), a(c) - a(c-1) = 0, for c = composite numbers (A002808). - Jaroslav Krizek, Mar 23 2009
a(n) = n^2/(2 log n) + O(n^2 log log n/log^2 n). - Vladimir Shevelev and Charles R Greathouse IV, May 29 2014
Conjecture: G.f.: Sum_{i>0} Sum_{j>=i} Sum_{k>=j|i-j+k is prime} x^k. - Benedict W. J. Irwin, Mar 31 2017
a(n) = (n+1)*A000720(n) - A046992(n). - Ridouane Oudra, Sep 18 2021
a(n) = A007504(A000720(n)). - Ridouane Oudra, Feb 22 2022
a(n) = Sum_{p<=n, p prime} p. - Wesley Ivan Hurt, Dec 31 2023

A179215 Product of squarefree numbers less than n+1.

Original entry on oeis.org

1, 1, 2, 6, 6, 30, 180, 1260, 1260, 1260, 12600, 138600, 138600, 1801800, 25225200, 378378000, 378378000, 6432426000, 6432426000, 122216094000, 122216094000, 2566537974000, 56463835428000, 1298668214844000, 1298668214844000, 1298668214844000, 33765373585944000

Offset: 0

Reinhard Zumkeller, Jul 05 2010

nonn

G. C. Greubel, Table of n, a(n) for n = 0..680

Cf. A013928, A066779, A005117, A008966, A179214.

Cf. A000142, A000720, A001221, A025487, A034386.

a:= proc(n) option remember; `if`(n=0, 1,
      a(n-1)*`if`(issqrfree(n), n, 1))
    end:
seq(a(n), n=0..27);  # Alois P. Heinz, Sep 20 2021

With[{sfnos=Select[Range[50],SquareFreeQ]},Table[Times@@Select[sfnos, #Harvey P. Dale, Jun 13 2011 *)

a(n) = prod(k=1, n, if (issquarefree(k), k, 1)); \\ Michel Marcus, Sep 20 2021

a(n) = my(p=1); forsquarefree(x=1, n, p*=x[1]); p; \\ Michel Marcus, Sep 20 2021

a(n) = Product_{k=1..n} k^A008966(k).
A001221(a(n)) = A000720(n).
Subsequence of A025487.
A034386(n) <= a(n) <= A000142(n).
A179214(n) = a(2*n)/a(n-1) for n>0.

Definition corrected by Harvey P. Dale, Jun 13 2011

A179213 Sum of squarefree numbers between n and 2*n (inclusive).

Original entry on oeis.org

3, 5, 14, 18, 28, 34, 55, 63, 80, 99, 132, 144, 170, 157, 202, 218, 285, 303, 378, 398, 481, 503, 527, 551, 551, 602, 629, 684, 799, 829, 922, 891, 1022, 1056, 1161, 1197, 1344, 1307, 1424, 1464, 1546, 1588, 1717, 1761, 1850, 1941, 2082, 2130, 2227, 2227

Offset: 1

Reinhard Zumkeller, Jul 05 2010

nonn

Harvey P. Dale, Table of n, a(n) for n = 1..1000

Cf. A005117, A045943, A066779, A073837, A179211, A179214.

Table[Total[Select[Range[n,2n],SquareFreeQ]],{n,50}] (* Harvey P. Dale, Apr 29 2017 *)

a(n) = Sum_{k=n..2*n} k*A008966(k).
A073837(n) <= a(n) <= A045943(n);
a(n) = A066779(2*n) - A066779(n-1).
a(n) ~ (9/Pi^2) * n^2 + O(n^(3/2)). - Amiram Eldar, Mar 07 2021

A262992 Sum of the squarefree numbers among the partition parts of n into two parts.

Original entry on oeis.org

0, 2, 3, 8, 6, 14, 17, 24, 24, 29, 34, 51, 45, 65, 72, 87, 87, 104, 104, 133, 123, 155, 166, 189, 189, 202, 215, 229, 215, 259, 274, 305, 305, 355, 372, 407, 407, 463, 482, 521, 521, 583, 604, 669, 647, 670, 693, 740, 740, 740, 740, 817, 791, 844, 844, 899

Offset: 1

Wesley Ivan Hurt, Oct 06 2015

			a(3)=3; there is one partition of 3 into two parts: (2,1). The sum of the squarefree parts of this partition is 2+1=3, so a(3)=3.
a(5)=6; there are two partitions of 5 into two parts: (4,1) and (3,2). The sum of the squarefree parts of these partitions is 3+2+1=6, so a(5)=6.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Index entries for sequences related to partitions

Cf. A066779, A008683, A071068, A261985, A262351, A262868, A262870, A262871, A262991.

with(numtheory): A262992:=n->add(i*mobius(i)^2 + (n-i)*mobius(n-i)^2, i=1..floor(n/2)): seq(A262992(n), n=1..100);

Table[Sum[i*MoebiusMu[i]^2 + (n - i)*MoebiusMu[n - i]^2, {i, Floor[n/2]}], {n, 100}]

vector(100, n, sum(k=1, n\2, k*moebius(k)^2 + (n-k)*moebius(n-k)^2)) \\ Altug Alkan, Oct 07 2015

a(n)=my(s, k2, m=n-1); forsquarefree(k=1, sqrtint(m), k2=k[1]^2; s+= k2*binomial(m\k2+1, 2)*moebius(k)); s + (n%4==2 && issquarefree(n/2))*n/2 \\ Charles R Greathouse IV, Jan 13 2018

a(n) = Sum_{i=1..floor(n/2)} i*mu(i)^2 + (n-i)*mu(n-i)^2, where mu is the Möebius function (A008683).

a(n) = A262870(n) + A262871(n).

A294285 Sum of the larger parts of the partitions of n into two distinct parts with larger part squarefree.

Original entry on oeis.org

0, 0, 2, 3, 3, 5, 11, 18, 18, 13, 23, 28, 28, 34, 48, 63, 63, 80, 80, 89, 89, 99, 121, 144, 144, 131, 157, 143, 143, 157, 187, 218, 218, 234, 268, 303, 303, 321, 359, 398, 398, 418, 460, 481, 481, 458, 504, 551, 551, 551, 551, 576, 576, 629, 629, 684, 684

Offset: 1

Wesley Ivan Hurt, Oct 26 2017

Sum of the lengths of the distinct rectangles with squarefree length and positive integer width such that L + W = n, W < L. For example, a(14) = 34; the rectangles are 1 X 13, 3 X 11, 4 X 10. The sum of the lengths is then 13 + 11 + 10 = 34. - Wesley Ivan Hurt, Nov 01 2017

			10 can be partitioned into two distinct parts as follows: (1, 9), (2, 8), (3, 7), (4, 6). The squarefree larger parts are 6 and 7, which sum to a(10) = 13. - _David A. Corneth_, Oct 27 2017

Harvey P. Dale, Table of n, a(n) for n = 1..1000
Index entries for sequences related to partitions

Cf. A005117, A008683, A066779, A211539, A262870.

Table[Sum[(n - i)*MoebiusMu[n - i]^2, {i, Floor[(n-1)/2]}], {n, 60}]
Table[Total[Select[IntegerPartitions[n,{2}],DuplicateFreeQ[#]&&SquareFreeQ[#[[1]]]&][[;;,1]]],{n,60}] (* Harvey P. Dale, Aug 30 2025 *)

first(n) = {my(res = vector(n, i, binomial(i, 2) - binomial(i\2+1, 2)), nsqrfr = List()); forprime(i=2, sqrtint(n), for(k = 1, n \ i^2, listput(nsqrfr, k*i^2))); listsort(nsqrfr, 1); for(i=1, #nsqrfr, for(m = nsqrfr[i]+1, min(2*nsqrfr[i]-1, n), res[m]-=nsqrfr[i])); res} \\ David A. Corneth, Oct 27 2017

a(n) = sum(i=1, (n-1)\2, (n-i)*moebius(n-i)^2); \\ Michel Marcus, Nov 08 2017

a(n) = Sum_{i=1..floor((n-1)/2)} (n - i) * mu(n - i)^2, where mu is the Möbius function (A008683).

a(n) = A211539(n + 1) - A294246(n). - David A. Corneth, Oct 27 2017

A362029 a(n) = Sum_{k=1..n} (-1)^(n-k) * k * mu(k)^2, where mu(k) is the Moebius function.

Original entry on oeis.org

1, 1, 2, -2, 7, -1, 8, -8, 8, 2, 9, -9, 22, -8, 23, -23, 40, -40, 59, -59, 80, -58, 81, -81, 81, -55, 55, -55, 84, -54, 85, -85, 118, -84, 119, -119, 156, -118, 157, -157, 198, -156, 199, -199, 199, -153, 200, -200, 200, -200, 251, -251, 304, -304, 359, -359, 416, -358, 417, -417, 478, -416, 416

Offset: 1

Seiichi Manyama, Apr 05 2023

Seiichi Manyama, Table of n, a(n) for n = 1..10000

Cf. A008683, A066779, A055615, A362021, A362028.

a(n) = sum(k=1, n, (-1)^(n-k)*k*moebius(k)^2);

G.f.: (Sum_{k>=1} mu(k)^2 * k * x^k) / (1 + x).

a(n) = -a(n-1) + |A055615(n)| for n > 1.

A294062 Sum of the differences of the larger and smaller parts in the partitions of 2n into two parts with the smaller part squarefree.

Original entry on oeis.org

0, 2, 6, 12, 18, 26, 36, 48, 60, 72, 86, 102, 118, 136, 156, 178, 200, 224, 248, 274, 300, 328, 358, 390, 422, 454, 488, 522, 556, 592, 630, 670, 710, 752, 796, 842, 888, 936, 986, 1038, 1090, 1144, 1200, 1258, 1316, 1374, 1434, 1496, 1558, 1620, 1682, 1746

Offset: 1

Wesley Ivan Hurt, Oct 22 2017

Sum of the slopes of the tangent lines along the left side of the parabola b(x) = 2*n*x-x^2 at squarefree values of x for x in 0 < x <= n. For example, d/dx 2*n*x-x^2 = 2n-2x. So for a(6), the squarefree values of x are x=1,2,3,5,6 and so a(6) = 12-2*1 + 12-2*2 + 12-2*3 + 12-2*5 + 12-2*6 = 10 + 8 + 6 + 2 = 26. - Wesley Ivan Hurt, Mar 25 2018

			For n = 4, 8 can be partitioned into two parts with the smaller part squarefree in three ways: 7 + 1, 6 + 2, and 5 + 3, so a(4) = (7 - 1) + (6 - 2) + (5 - 3) = 12. - _Michael B. Porter_, Mar 27 2018

Index entries for sequences related to partitions

Cf. A008683 (mu), A008966, A013928, A066779.

Table[2*Sum[(n - i) MoebiusMu[i]^2, {i, n}], {n, 80}]

a(n) = 2 * sum(i=1, n, (n-i)*issquarefree(i)); \\ Michel Marcus, Mar 26 2018

a(n) = 2 * Sum_{i=1..n} (n - i) * mu(i)^2, where mu is the Möbius function (A008683).

a(n) = 2*(n*A013928(n) - A066779(n)). - Wesley Ivan Hurt, Jul 08 2025

cp's OEIS Frontend

A013928 Number of (positive) squarefree numbers < n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

PARI

PARI

Python

Python

Formula

A034387 Sum of primes <= n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

PARI

Python

Formula

A179215 Product of squarefree numbers less than n+1.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions

A179213 Sum of squarefree numbers between n and 2*n (inclusive).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A262992 Sum of the squarefree numbers among the partition parts of n into two parts.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

A294285 Sum of the larger parts of the partitions of n into two distinct parts with larger part squarefree.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs