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,8

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

Links

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

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

Example

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}.

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

Prog

(Scheme) (define (A057627 n) (- n (A013928 (+ n 1))))
(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

Crossrefs

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

Sequence in context: A106742 A106733 A087838 * A013940 A029129 A087842

Adjacent sequences: A057624 A057625 A057626 * A057628 A057629 A057630

Keyword

nonn,easy

Author

Labos Elemer, Oct 10 2000

Extensions

Offset and formula corrected by Antti Karttunen, Jun 03 2014

Status

approved