A143658 -id:A143658 - cp's OEIS frontend

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

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

A373415 Maximum of the n-th maximal run of squarefree numbers.

Original entry on oeis.org

3, 7, 11, 15, 17, 19, 23, 26, 31, 35, 39, 43, 47, 51, 53, 55, 59, 62, 67, 71, 74, 79, 83, 87, 89, 91, 95, 97, 103, 107, 111, 115, 119, 123, 127, 131, 134, 139, 143, 146, 149, 151, 155, 159, 161, 163, 167, 170, 174, 179, 183, 187, 191, 195, 197, 199, 203, 206

Offset: 1

Gus Wiseman, Jun 05 2024

nonn

The minimum is given by A072284.
A run of a sequence (in this case A005117) is an interval of positions at which consecutive terms differ by one.
Consists of all squarefree numbers k such that k + 1 is not squarefree.

			Row-maxima of:
   1   2   3
   5   6   7
  10  11
  13  14  15
  17
  19
  21  22  23
  26
  29  30  31
  33  34  35
  37  38  39
  41  42  43
  46  47
  51
  53
  55
  57  58  59

Gus Wiseman, Four statistics for runs and antiruns of prime, nonprime, squarefree, and nonsquarefree numbers

Functional neighbors: A006093, A007674, A067774, A072284, A120992, A373413.
A005117 lists the squarefree numbers, first differences A076259.
A013929 lists the nonsquarefree numbers, first differences A078147.
Cf. A049093, A049094, A061398, A069010, A077641, A077643, A112925, A112926, A143658, A372683, A373125, A373126.

Last/@Split[Select[Range[100],SquareFreeQ],#1+1==#2&]//Most

a(n) = A070321(A072284(n+1) - 1).

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

A373414 Sum of the n-th maximal run of nonsquarefree numbers differing by one.

Original entry on oeis.org

4, 17, 12, 16, 18, 20, 49, 55, 32, 36, 40, 89, 147, 52, 54, 56, 60, 127, 68, 72, 151, 161, 84, 88, 90, 92, 96, 297, 104, 108, 112, 233, 241, 375, 128, 132, 271, 140, 144, 295, 150, 305, 156, 160, 162, 164, 337, 343, 351, 180, 184, 377, 192, 196, 198, 200, 204

Offset: 1

Gus Wiseman, Jun 06 2024

nonn

The length of this run is given by A053797.

A run of a sequence (in this case A013929) is an interval of positions at which consecutive terms differ by one.

			Row-sums of:
   4
   8   9
  12
  16
  18
  20
  24  25
  27  28
  32
  36
  40
  44  45
  48  49  50

Gus Wiseman, Four statistics for runs and antiruns of prime, nonprime, squarefree, and nonsquarefree numbers

The partial sums are a subset of A329472.
Functional neighbors: A053797, A053806, A054265, A373406, A373412, A373413.
A005117 lists the squarefree numbers, first differences A076259.
A013929 lists the nonsquarefree numbers, first differences A078147.
Cf. A049093, A049094, A061398, A061399, A077641, A077643, A101836, A143658 A294242, A373123, A373197.

Total/@Split[Select[Range[100],!SquareFreeQ[#]&],#1+1==#2&]//Most

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

A372403 Number of k < 2^n that are neither squarefree nor prime powers.

Original entry on oeis.org

1, 5, 16, 37, 83, 178, 374, 772, 1565, 3160, 6361, 12770, 25599, 51265, 102634, 205374, 410873, 821924, 1644070, 3288433, 6577231, 13154868, 26310347, 52621521, 105244142, 210489792, 420981295, 841964929, 1683933254, 3367871086, 6735748322, 13471504796, 26943020642

Offset: 4

Michael De Vlieger, Jun 09 2024

Analogous to A143658 (number of squarefree k <= 2^n) and A182908 (position of 2^n among prime powers A246655).

			Let quality Q represent a number k that is neither squarefree nor prime power. For instance, Q(k) is true if and only if Omega(k) > omega(k) > 1, i.e., A001222(k) > A001221(k) > 1.
a(4) = 1 since there is one number k = 12 such that Q(k) is true; 12 < 2^4.
a(5) = 5 since there are 5 numbers k such that Q(k) is true; {12, 18, 20, 24, 28} are less than 2^5.
a(6) = 16 since A126706(16) < 2^6 < A126706(17), etc.

Chai Wah Wu, Table of n, a(n) for n = 4..70

Cf. A007053, A036386, A126706, A143658, A182908.

filter:= proc(n) local F;
  F:= ifactors(n)[2];
  nops(F) > 1 and max(F[..,2]) > 1
end proc:
R:= NULL: v:= 0:
for i from 4 to 20 do
  v:= v + nops(select(filter, [$2^(i-1)+1 .. 2^i-1]));
  R:= R,v;
od:
R; # Robert Israel, Jun 09 2024

Table[2^n - Sum[PrimePi@Floor[2^(n/k)], {k, 2, n}] - Sum[MoebiusMu[k]*Floor[#/(k^2)], {k, Floor[Sqrt[#]]}] &[2^n], {n, 4, 36} ] (* Michael De Vlieger, Jan 24 2025 *)

from math import isqrt
from sympy import mobius, nextprime, integer_log
def A372403(n):
    m, p = (1<Chai Wah Wu, Jun 10 2024

a(n) = 2^n - A036386(n) - A143658(n). - Michael De Vlieger, Jan 24 2025

a(30) onwards from Chai Wah Wu, Jun 10 2024

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

A373124 Sum of indices of primes between powers of 2.

Original entry on oeis.org

1, 2, 7, 11, 45, 105, 325, 989, 3268, 10125, 33017, 111435, 369576, 1277044, 4362878, 15233325, 53647473, 189461874, 676856245, 2422723580, 8743378141, 31684991912, 115347765988, 421763257890, 1548503690949, 5702720842940, 21074884894536, 78123777847065

Offset: 0

Gus Wiseman, May 31 2024

nonn

Sum of k such that 2^n+1 <= prime(k) <= 2^(n+1).

			Row-sums of the sequence of all positive integers as a triangle with row-lengths A036378:
   1
   2
   3  4
   5  6
   7  8  9 10 11
  12 13 14 15 16 17 18
  19 20 21 22 23 24 25 26 27 28 29 30 31
  32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54

For indices of primes between powers of 2:
- sum A373124 (this sequence)
- length A036378
- min A372684 (except initial terms), delta A092131
- max A007053
For primes between powers of 2:
- sum A293697
- length A036378
- min A104080 or A014210
- max A014234, delta A013603
For squarefree numbers between powers of 2:
- sum A373123
- length A077643, run-lengths of A372475
- min A372683, delta A373125, indices A372540
- max A372889, delta A373126, indices A143658
Cf. A000040, A000120, A014499, A029837, A029931, A035100, A069010, A070939, A112925, A112926, A211997.

Table[Total[PrimePi/@Select[Range[2^(n-1)+1,2^n],PrimeQ]],{n,10}]

ip(n) = primepi(1<A007053
t(n) = n*(n+1)/2; \\ A000217
a(n) = t(ip(n+1)) - t(ip(n)); \\ Michel Marcus, May 31 2024

A376164 Maximum of the n-th maximal run of nonsquarefree numbers (increasing by 1 at a time).

Original entry on oeis.org

4, 9, 12, 16, 18, 20, 25, 28, 32, 36, 40, 45, 50, 52, 54, 56, 60, 64, 68, 72, 76, 81, 84, 88, 90, 92, 96, 100, 104, 108, 112, 117, 121, 126, 128, 132, 136, 140, 144, 148, 150, 153, 156, 160, 162, 164, 169, 172, 176, 180, 184, 189, 192, 196, 198, 200, 204, 208

Offset: 1

Gus Wiseman, Sep 15 2024

nonn

			The maximal runs of nonsquarefree numbers begin:
       4
     8   9
      12
      16
      18
      20
    24  25
    27  28
      32
      36
      40
    44  45
  48  49  50

For length instead of maximum we have A053797 (firsts A373199).
For lengths of anti-runs we have A373409 (firsts A373573).
For sum instead of maximum we have A373414, anti A373412.
For minimum instead of maximum we have A053806, anti A373410.
For anti-runs instead of runs we have A068781.
For squarefree instead of nonsquarefree we have A373415, anti A007674.
For nonprime instead of nonsquarefree we have A006093 with 2 removed.
A005117 lists the squarefree numbers, first differences A076259.
A013929 lists the nonsquarefree numbers, differences A078147, sums A329472.
A061398 counts squarefree numbers between primes, nonsquarefree A061399.
A120992 gives squarefree run-lengths, anti A373127 (firsts A373128).
A373413 adds up each maximal run of squarefree numbers, min A072284.
A375707 counts squarefree numbers between consecutive nonsquarefree numbers.
Cf. A000040, A020754, A045882, A049094, A054265, A077641, A101836, A143658, A294242, A375709.

Max/@Split[Select[Range[100],!SquareFreeQ[#]&],#1+1==#2&]//Most

A256942 Number of odd squarefree numbers <= 2^n.

Original entry on oeis.org

1, 1, 2, 4, 7, 13, 26, 52, 105, 209, 415, 830, 1661, 3321, 6641, 13279, 26565, 53123, 106237, 212488, 424973, 849945, 1699889, 3399761, 6799540, 13599124, 27198203, 54396423, 108792774, 217585510, 435171212, 870342371, 1740684723, 3481369358, 6962738693, 13925477442

Offset: 0

Robert Israel, Apr 13 2015

nonn

Number of oddly squarefree (A122132) numbers in each new tier > 2^(n-1). - Travis Scott, Jan 14 2023

a(n) is also the number of even squarefree numbers <= 2^(n+1). - Amiram Eldar, Feb 20 2023

			For n=4 there are 7 odd squarefree numbers <= 2^4, namely 1,3,5,7,11,13,15.
For oddly squarefree we have 2^3 < 10,11,12,13,14,15,16 <= 2^4.

Chai Wah Wu, Table of n, a(n) for n = 0..73 (terms 0..64 from Amiram Eldar)

Cf. A008683, A039956, A056911, A065359, A122132, A143658.

g:= proc(n) option remember; local L ; L := convert(n, base, 2) ; (2*n - add( L[i]*(-1)^i, i=1..nops(L)))/3 ; end proc:
a:= n -> add(numtheory:-mobius(i)*g(floor(2^n/i^2)),i=1..floor(2^(n/2))):
seq(a(n),n=0..32);

A143658[n_] := Sum[MoebiusMu[i] Floor[2^n/i^2], {i, 1, 2^(n/2)}];
a[n_] := Sum[(-1)^j A143658[n-j], {j, 0, n}];
Table[a[n], {n, 0, 32}] (* Jean-François Alcover, Sep 22 2022 *)

a(n) = Sum_{j=0..n} (-1)^j*A143658(n-j).
a(n) = (2/3) * A143658(n) + (1/3) * Sum_{i=1..floor(2^(n/2))} A008683(i)*A065359(floor(2^n/i^2)).
a(n) + a(n+1) = A143658(n+1).
a(n) ~ 2^(n+2)/Pi^2. - Amiram Eldar, Feb 20 2023

a(33)-a(35) from Amiram Eldar, Feb 20 2023

cp's OEIS Frontend

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Python

Formula

Extensions

A373415 Maximum of the n-th maximal run of squarefree numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A160113 Number of cubefree integers not exceeding 2^n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

Python

Python

Formula

A373414 Sum of the n-th maximal run of nonsquarefree numbers differing by one.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A160112 Number of cubefree integers not exceeding 10^n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Python

Formula

A372403 Number of k < 2^n that are neither squarefree nor prime powers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

Extensions

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

Views