A071172 -id:A071172 - cp's OEIS frontend

A143658 Number of squarefree integers not exceeding 2^n.

1, 2, 3, 6, 11, 20, 39, 78, 157, 314, 624, 1245, 2491, 4982, 9962, 19920, 39844, 79688, 159360, 318725, 637461, 1274918, 2549834, 5099650, 10199301, 20398664, 40797327, 81594626, 163189197, 326378284, 652756722, 1305513583, 2611027094

Offset: 0

M. F. Hasler, Aug 28 2008

nonn

Except for the first 2 terms, it would not make a difference to replace "not exceeding" by "less than": that sequence would start 0,1,3,6,11,20,39,78,...

			a(4) = 11 since there are the 11 squarefree integers {1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15} not exceeding 2^4=16.

Chai Wah Wu, Table of n, a(n) for n = 0..73 (terms 0..58 from Gerard P. Michon, terms 59..64 from Peter Polm)
Project Euler, Problem 193: Squarefree Numbers
G. P. Michon, On the number of squarefree integers not exceeding N. - _Gerard P. Michon_, Apr 30 2009

Cf. A005117, A013928, A071172, A053462.

c = 0; k = 1; lst = {1}; Do[ While[k <= 2^n, If[ SquareFreeQ@k, c++ ]; k++ ]; AppendTo[lst, c], {n, 27}] (* Robert G. Wilson v, Aug 31 2008 *)

print1(s=1);for(p=1,20,print1(", ",s+=sum(k=2^(p-1)+1, 2^p, issquarefree(k))))

a(n)=sum(d=1,sqrtint(n=2^n),moebius(d)*n\d^2) \\ Charles R Greathouse IV, Nov 14 2012

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

from math import isqrt
from sympy import mobius
def A143658(n):
    m = 1<Chai Wah Wu, Jun 01 2024

a(n) = Sum for i = 1 to 2^(n/2) of A008683(i)*floor(2^n/i^2). - Gerard P. Michon, Apr 30 2009

The limit of a(n)/2^n is 6/Pi^2. - Gerard P. Michon, Apr 30 2009

5 more terms from Robert G. Wilson v, Aug 31 2008

More terms from Alexis Olson (AlexisOlson(AT)gmail.com), Nov 08 2008

A053462 Number of positive squarefree integers less than 10^n.

Original entry on oeis.org

0, 6, 61, 608, 6083, 60794, 607926, 6079291, 60792694, 607927124, 6079270942, 60792710280, 607927102274, 6079271018294, 60792710185947, 607927101854103, 6079271018540405, 60792710185403794, 607927101854022750, 6079271018540280875, 60792710185402613302

Offset: 0

Harvey P. Dale, Aug 01 2001

nonn

			There are 608 squarefree integers smaller than 1000.

Amiram Eldar, Table of n, a(n) for n = 0..36 (from the b-file at A071172; terms 0..20 from Charles R Greathouse IV)
Gérard P. Michon, On the number of squarefree integers not exceeding N.

Cf. A005117, A013928.
Cf. A059956, A063035.
Apart from first two terms, same as A071172.
Binary counterpart is A143658. - Gerard P. Michon, Apr 30 2009

a[n_] := Module[{t=10^n-1}, Sum[MoebiusMu[k]Floor[t/k^2], {k, 1, Sqrt[t]}]]

a(n)=sum(d=1,sqrtint(n=10^n-1), n\d^2*moebius(d)) \\ Charles R Greathouse IV, Nov 14 2012

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

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

a(n)/10^n = (6/Pi^2)*(1+o(1)), cf. A059956.

a(n) = A071172(n) - [n <= 1] where [] is the Iverson bracket. - Chai Wah Wu, Jun 01 2024

More terms from Dean Hickerson and Vladeta Jovovic, Aug 06 2001
One more term from Jud McCranie, Sep 01 2005
a(0)=0 and a(14)-a(17) from Gerard P. Michon, Apr 30 2009
a(18)-a(20) from Charles R Greathouse IV, Jan 08 2018

A160113 Number of cubefree integers not exceeding 2^n.

Original entry on oeis.org

1, 2, 4, 7, 14, 27, 54, 107, 214, 427, 854, 1706, 3410, 6815, 13629, 27259, 54521, 109042, 218080, 436158, 872318, 1744638, 3489278, 6978546, 13957092, 27914186, 55828364, 111656716, 223313428, 446626866, 893253744, 1786507472, 3573014938, 7146029910, 14292059832

Offset: 0

Gerard P. Michon, May 02 2009

An alternate definition specifying "less than 2^n" would yield the same sequence except for the first 3 terms: 0,1,3,7,14,27,54,107, etc. (since powers of 2 beyond 8 are not cubefree).

The limit of a(n)/2^n is the inverse of Apery's constant, 1/zeta(3) [see A088453].

			a(0)=1 because there is just one cubefree integer (1) not exceeding 2^0 = 1.
a(3)=7 because 1,2,3,4,5,6,7 are cubefree but 8 is not.

Chai Wah Wu, Table of n, a(n) for n = 0..103 (terms 0..80 from Gerard P. Michon)
Gerard P. Michon, On the number of cubefree integers not exceeding N.

Cf. A004709 (cubefree numbers), A160112 (decimal counterpart for cubefree integers), A143658 (binary counterpart for squarefree integers), A071172 & A053462 (decimal counterpart for squarefree integers).

Cf. A060431.

a160113 = a060431 . (2 ^)  -- Reinhard Zumkeller, Jul 27 2015

a[n_] := Sum[ MoebiusMu[i]*Floor[2^n/i^3], {i, 1, 2^(n/3)}]; Table[a[n], {n, 0, 32}] (* Jean-François Alcover, Dec 20 2011, from formula *)
Module[{nn=20,mu},mu=Table[If[Max[FactorInteger[n][[All,2]]]<3,1,0],{n,2^nn}];Table[Total[Take[mu,2^k]],{k,0,nn}]] (* The program generates the first 20 terms of the sequence. To get more, increase the value (constant) for nn, but the program may take a long time to run. *) (* Harvey P. Dale, Aug 13 2021 *)

from sympy import mobius, integer_nthroot
def A160113(n): return sum(mobius(k)*((1<Chai Wah Wu, Aug 06 2024

from bitarray import bitarray
from sympy import integer_nthroot
def A160113(n): # faster program
    q = 1<Chai Wah Wu, Aug 06 2024

a(n) = Sum_{i=1..2^(n/3)} A008683(i)*floor(2^n/i^3).

A160112 Number of cubefree integers not exceeding 10^n.

Original entry on oeis.org

1, 9, 85, 833, 8319, 83190, 831910, 8319081, 83190727, 831907372, 8319073719, 83190737244, 831907372522, 8319073725828, 83190737258105, 831907372580692, 8319073725807178, 83190737258070643, 831907372580707771

Offset: 0

Gerard P. Michon, May 02 2009, May 06 2009

An alternate definition specifying "less than 10^n" would yield the same sequence except for the first 3 terms: 0, 8, 84, 833, 8319, etc. (since powers of 10 beyond 1000 are not cubefree anyhow).

The limit of a(n)/10^n is the inverse of Apery's constant, 1/zeta(3), whose digits are given by A088453.

			a(0)=1 because 1 <= 10^0 is not a multiple of the cube of a prime.
a(1)=9 because the 9 numbers 1,2,3,4,5,6,7,9,10 are cubefree; 8 is not.
a(2)=85 because there are 85 cubefree integers equal to 100 or less.
a(3)=833 because there are 833 cubefree integers below 1000 (which is not cubefree itself).

Chai Wah Wu, Table of n, a(n) for n = 0..31 (terms 0..29 from Gerard P. Michon)
Gerard P. Michon, On the number of cubefree integers not exceeding N.

A004709 (cubefree numbers). A088453 (limit of the string of digits). A160113 (binary counterpart for cubefree integers). A071172 & A053462 (decimal counterpart for squarefree integers). A143658 (binary counterpart for squarefree integers).

with(numtheory): A160112:=n->add(mobius(i)*floor(10^n/(i^3)), i=1..10^n): (1,9,85,seq(A160112(n), n=3..5)); # Wesley Ivan Hurt, Aug 01 2015

Table[ Sum[ MoebiusMu[x]*Floor[10^n/(x^3)], {x, 10^(n/3)}], {n, 0, 18}] (* Robert G. Wilson v, May 27 2009 *)

from sympy import mobius, integer_nthroot
def A160112(n): return sum(mobius(k)*(10**n//k**3) for k in range(1, integer_nthroot(10**n,3)[0]+1)) # Chai Wah Wu, Aug 06 2024

from bitarray import bitarray
from sympy import integer_nthroot
def A160112(n): # faster program
    q = 10**n
    m = integer_nthroot(q,3)[0]+1
    a, b = bitarray(m), bitarray(m)
    a[1], p, i, c = 1, 2, 4, q-sum(q//k**3 for k in range(2,m))
    while i < m:
        j = 2
        while i < m:
            if j==p:
                c -= (b[i]^1 if a[i] else -1)*(q//i**3)
                j, a[i], b[i] = 0, 1, 1
            else:
                t1, t2 = a[i], b[i]
                if (t1&t2)^1:
                    a[i], b[i] = (t1^1)&t2, ((t1^1)&t2)^1
                    c += (t2 if t1 else 2)*(q//i**3) if (t1^1)&t2 else (t2-2 if t1 else 0)*(q//i**3)
            i += p
            j += 1
        p += 1
        while a[p]|b[p]:
            p += 1
        i = p<<1
    return c # Chai Wah Wu, Aug 06 2024

a(n) = Sum_{i=1..floor(10^(n/3))} A008683(i)*floor(10^n/i^3).

A063035 Number of integers m <= 10^n that contain a square factor (i.e., belong to A013929).

Original entry on oeis.org

3, 39, 392, 3917, 39206, 392074, 3920709, 39207306, 392072876, 3920729058, 39207289720, 392072897726, 3920728981706, 39207289814053, 392072898145897, 3920728981459595

Offset: 1

Robert G. Wilson v, Aug 02 2001

nonn

Note that "containing a square factor" (A013929) is different from "squareful" (A001694).

Robert G. Wilson v, Table of n, a(n) for n = 1..36

Cf. A001694, A013929, A229099.

For the complementary counts see A053462 and A071172.

f[n_] := Sum[-MoebiusMu[i]Floor[n/i^2], {i, 2, Sqrt@ n}]; Table[ f[10^n], {n, 0, 14}]

{ default(realprecision, 50); for (n=1, 100, t=10^n - 1; a=10^n - sum(k=1, sqrt(t), moebius(k)*floor(t/k^2)); write("b063035.txt", n, " ", a) ) } \\ Harry J. Smith, Aug 16 2009

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

Limit_{n->oo} a(n)/10^n = A229099. - Robert G. Wilson v, Aug 12 2014

a(n) = 10^n - A071172(n). - Amiram Eldar, Mar 10 2024

More terms from Harry J. Smith, Aug 16 2009

Edited (with a more precise definition and a new value for a(1)) by N. J. A. Sloane, Aug 06 2012. As a result of this change, the programs probably now give the wrong value for a(1). The source of the trouble was the ambiguous meaning of squareful - the official definition of squareful is A001694.

A087618 a(n) is the number of pair of consecutive numbers (k,k+1) with k<=10^n such that k and k+1 are both squarefree.

Original entry on oeis.org

1, 5, 33, 323, 3230, 32269, 322619, 3226343, 32263377, 322634281, 3226340896, 32263409594, 322634100659, 3226340989192

Offset: 0

Eric W. Weisstein, Sep 19 2003

Eric Weisstein's World of Mathematics, Squarefree

Cf. A071172, A065474.

Asymptotic density is A065474.

a(11)-a(13) from Donovan Johnson, Jun 26 2010

A274264 Number of squarefree integers congruent to {5, 6, 7} mod 8 <= 10^n.

Original entry on oeis.org

3, 33, 308, 3050, 30405, 303979, 3039648, 30396356, 303963597, 3039635407, 30396354916, 303963551200, 3039635509025, 30396355093247, 303963550927371, 3039635509273730, 30396355092701463, 303963550927001730

Offset: 1

Frank M Jackson, Jun 16 2016

Empirically, the limit of a(n)/10^n tends to 3/Pi^2 (A104141) and implies that the asymptotic density of squarefree numbers congruent to {5, 6, 7} mod 8 is half that of the asymptotic density of all squarefree integers (A071172). There is a slight bias towards more squarefree numbers congruent to {5, 6, 7} mod 8 that can be argued heuristically as {1, 2, 3} mod 8 contains a square residue and its equivalence class should contain less squarefree numbers.

Also it has been shown, conditional on the Birch Swinnerton-Dyer conjecture, that all squarefree integers congruent to {5, 6, 7} mod 8 (A273929) are primitive (squarefree) congruent numbers (A006991). However, this property applies only sparsely to squarefree integers congruent to {1, 2, 3} mod 8 (A062695).

Keith Conrad, The Congruent Number Problem, The Harvard College Mathematics Review, (2008).
Eric Weisstein's World of Mathematics, Squarefree
Shou-Wu Zhang, The Congruent Numbers and Heegner Points, Asian Pacific Mathematics Newsletter, Vol 3(2) (2013).

Cf. A006991, A062695, A071172, A104141, A273929.

Table[Length@Select[Range[10^n], MemberQ[{5, 6, 7}, Mod[#, 8]]&& SquareFreeQ[#] &], {n, 1, 8}]

a(10)-a(11) from Giovanni Resta, Jun 17 2016

a(7) corrected and a(12)-a(18) added by Hiroaki Yamanouchi, Dec 25 2016

A113544 Numbers simultaneously pentagon-free, squarefree and triangle-free.

Original entry on oeis.org

1, 2, 7, 11, 13, 14, 17, 19, 23, 26, 29, 31, 34, 37, 38, 41, 43, 46, 47, 53, 58, 59, 61, 62, 67, 71, 73, 74, 77, 79, 82, 83, 86, 89, 94, 97, 101, 103, 106, 107, 109, 113, 118, 119, 122, 127, 131, 133, 134, 137, 139, 142, 143, 146, 149, 151, 157, 158, 161, 163

Offset: 1

Jonathan Vos Post, Jan 13 2006

Bellman, R. and Shapiro, H. N. "The Distribution of Squarefree Integers in Small Intervals." Duke Math. J. 21, 629-637, 1954.
Borwein, J. and Bailey, D. Mathematics by Experiment: Plausible Reasoning in the 21st Century. Natick, MA: A. K. Peters, 2003.
Hardy, G. H. and Wright, E. M. "The Number of Squarefree Numbers." Section 18.6 in An Introduction to the Theory of Numbers, 5th ed. Oxford, England: Clarendon Press, pp. 269-270, 1979.

G. C. Greubel and Charles R Greathouse IV, Table of n, a(n) for n = 1..10000 (first 1000 terms from Greubel)
Eric Weisstein's World of Mathematics, Squarefree.

Cf. A000217, A005117, A113502, A013929, A046098, A059956, A065474, A071172, A087618, A088454, A112886, A113508.

bad = Rest@ Union[# (# + 1)/2 &@ Range[19], Range[14]^2, # (3 # - 1)/2 &@ Range[11]]; Select[Range[200], {} == Intersection[bad, Divisors[#]] &] (* Giovanni Resta, Jun 13 2016 *)

list(lim)=my(v=List()); forsquarefree(n=1,lim\1, fordiv(n,d, if((ispolygonal(d,3) || ispolygonal(d,5)) && d>1, next(2))); listput(v,n[1])); Vec(v); \\ Charles R Greathouse IV, Dec 24 2018

a(n) has no factor >1 of form a*(a+1)/2 nor b^2 nor c*(3*c-1)/2. A005117 INTERSECTION A112886 INTERSECTION A113508.

Corrected and extended by Giovanni Resta, Jun 13 2016

A158341 a(n) = A013928(A002110(n)).

Original entry on oeis.org

0, 1, 4, 18, 128, 1404, 18261, 310346, 5896727, 135624239, 3933101823, 121926157640, 4511267827531, 184961980943492, 7953365180610400, 373808163488684049, 19811832664899731265, 1168898127229083969892

Offset: 0

Mats Granvik, Mar 16 2009

Cf. A002110, A013928, A071172, A143658, A380403.

Table[-1 + Sum[MoebiusMu[k]*Floor[#/(k^2)], {k, Floor[Sqrt[#]]}] &[Product[Prime[i], {i, n}]], {n, 0, 12}] (* Michael De Vlieger, Jan 24 2025 *)

a(n) = my(t=vecprod(primes(n))-1); sum(i=1, sqrtint(t), t\i^2*moebius(i)); \\ Jinyuan Wang, Jan 24 2025

from math import isqrt
from sympy import primorial, mobius
def A158341(n):
    if n == 0: return 0
    m = primorial(n)-1
    return sum(mobius(k)*(m//k**2) for k in range(1,isqrt(m)+1)) # Chai Wah Wu, Jan 25 2025

a(n) = -1 + Sum_{i=1..floor(sqrt(A002110(n)))} moebius(i)*floor(A002110(n)/i^2). - Jinyuan Wang, Jan 24 2025

Extended and offset corrected by Max Alekseyev, Sep 13 2009
a(15) from Michael De Vlieger, Jan 24 2025
a(16)-a(17) from Chai Wah Wu, Jan 25 2025

A381391 Number of k <= 10^n that are neither squarefree nor prime powers (i.e., k is in A126706).

Original entry on oeis.org

0, 29, 367, 3866, 39098, 391838, 3920154, 39205902, 392069187, 3920718974, 39207261564, 392072817656, 3920728751139, 39207289143932, 392072896183208, 3920728975677128, 39207289797472001, 392072898095046811, 3920728981307675534, 39207289814141997459, 392072898144605471040

Offset: 1

Michael De Vlieger, Feb 22 2025

nonn

			Let S = A126706.
a(1) = 0 since the smallest term in S is 12.
a(2) = 29 since S(1..29) = {12, 18, 20, 24, ..., 99, 100}, etc.

Cf. A011557, A071172, A126706, A267574, A372403, A229099, A380403.

Table[10^n - Sum[PrimePi@ Floor[10^(n/k)], {k, 2, Floor[Log2[10^n]]}] - Sum[MoebiusMu[k]*Floor[10^n/(k^2)], {k, Floor[Sqrt[10^n]]}], {n, 10}]

from math import isqrt
from sympy import primepi, integer_nthroot, mobius
def A381391(n):
    m = 10**n
    return int(-sum(primepi(integer_nthroot(m,k)[0]) for k in range(2,m.bit_length()))-sum(mobius(k)*(m//k**2) for k in range(2, isqrt(m)+1))) # Chai Wah Wu, Feb 23 2025

a(n) = 10^n - Sum_{k = 2..log_2(10^n)} pi(floor(10^(n/k))) - Sum_{k = 1..floor(sqrt(10^n))} mu(k)*floor(10^n/k^2), where pi = A000720 and mu = A008683.

a(n) = A011557(n) - A071172(n) - A267574(n).

cp's OEIS Frontend

A143658 Number of squarefree integers not exceeding 2^n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

Python

Formula

Extensions

A053462 Number of positive squarefree integers less than 10^n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Python

Formula

Extensions

A160113 Number of cubefree integers not exceeding 2^n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

Python

Python

Formula

A160112 Number of cubefree integers not exceeding 10^n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Python

Formula

A063035 Number of integers m <= 10^n that contain a square factor (i.e., belong to A013929).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

A087618 a(n) is the number of pair of consecutive numbers (k,k+1) with k<=10^n such that k and k+1 are both squarefree.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions