A057627 Number of nonsquarefree numbers not exceeding n.

0, 0, 0, 1, 1, 1, 1, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 6, 6, 7, 7, 7, 7, 8, 9, 9, 10, 11, 11, 11, 11, 12, 12, 12, 12, 13, 13, 13, 13, 14, 14, 14, 14, 15, 16, 16, 16, 17, 18, 19, 19, 20, 20, 21, 21, 22, 22, 22, 22, 23, 23, 23, 24, 25, 25, 25, 25, 26, 26, 26, 26, 27, 27, 27, 28, 29, 29, 29

Offset: 1

Author

Labos Elemer, Oct 10 2000

Keywords

• nonn
• easy

Comments

Number of integers k in A013929 in the range 1 <= k <= n.

This sequence is different from A013940, albeit the first 35 terms are identical.

Asymptotic to k*n where k = 1 - 1/zeta(2) = 1 - 6/Pi^2 = A229099. - Daniel Forgues, Jan 28 2011

This sequence is the sequence of partial sums of A107078 (not of A056170). - Jason Kimberley, Feb 01 2017

Number of partitions of 2n into two parts with the smallest part nonsquarefree. - Wesley Ivan Hurt, Oct 25 2017

Examples

			a(36)=13 because 13 nonsquarefree numbers exist which do not exceed 36:{4,8,9,12,16,18,20,24,25,27,28,32,36}.
		

Links

• Robert Israel, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A005117, A008683, A013929, A013940, A013928, A002321, A028442, A107078, A229099, A294242.

Programs

Maple

N:= 1000: # to get terms up to a(N)
B:= Array(1..N, numtheory:-issqrfree):
C:= map(`if`,B,0,1):
A:= map(round,Statistics:-CumulativeSum(C)):
seq(A[n],n=1..N); # Robert Israel, Jun 03 2014

Mathematica

Accumulate[Table[If[SquareFreeQ[n],0,1],{n,80}]] (* Harvey P. Dale, Jun 04 2014 *)

PARI

a(n) = my(s=0); forsquarefree(k=1, sqrtint(n), s += (-1)^(#k[2]~) * (n\k[1]^2)); n - s; \\ Charles R Greathouse IV, May 18 2015; corrected by Daniel Suteu, May 11 2023

Python

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

Scheme

(define (A057627 n) (- n (A013928 (+ n 1))))

Formula

a(n) = n - A013928(n+1) = n - Sum_{k=1..n} mu(k)^2.

G.f.: Sum_{k>=1} (1 - mu(k)^2)*x^k/(1 - x). - Ilya Gutkovskiy, Apr 17 2017

Extensions

Offset and formula corrected by Antti Karttunen, Jun 03 2014