A057627 -id:A057627 - cp's OEIS frontend

A379306 Number of squarefree prime indices of n.

0, 1, 1, 2, 1, 2, 0, 3, 2, 2, 1, 3, 1, 1, 2, 4, 1, 3, 0, 3, 1, 2, 0, 4, 2, 2, 3, 2, 1, 3, 1, 5, 2, 2, 1, 4, 0, 1, 2, 4, 1, 2, 1, 3, 3, 1, 1, 5, 0, 3, 2, 3, 0, 4, 2, 3, 1, 2, 1, 4, 0, 2, 2, 6, 2, 3, 1, 3, 1, 2, 0, 5, 1, 1, 3, 2, 1, 3, 1, 5, 4, 2, 1, 3, 2, 2, 2

Offset: 1

Gus Wiseman, Dec 25 2024

nonn

A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.

			The prime indices of 39 are {2,6}, so a(39) = 2.
The prime indices of 70 are {1,3,4}, so a(70) = 2.
The prime indices of 98 are {1,4,4}, so a(98) = 1.
The prime indices of 294 are {1,2,4,4}, a(294) = 2.
The prime indices of 1911 are {2,4,4,6}, so a(1911) = 2.
The prime indices of 2548 are {1,1,4,4,6}, so a(2548) = 3.

Positions of first appearances are A000079.
Positions of zero are A379307, counted by A114374 (strict A256012).
Positions of one are A379316, counted by A379308 (strict A379309).
A000040 lists the primes, differences A001223.
A005117 lists the squarefree numbers, differences A076259.
A008966 is the characteristic function for the squarefree numbers.
A013929 lists the nonsquarefree numbers, differences A078147.
A055396 gives least prime index, greatest A061395.
A056239 adds up prime indices, row sums of A112798, counted by A001222.
A061398 counts squarefree numbers between primes, zeros A068360.
A377038 gives k-th differences of squarefree numbers.
Other counts of prime indices:
- A087436 postpositive, see A038550.
- A257991 odd, see A000041, A000070, A066207, A349158.
- A257992 even, see A000009, A038348, A066208, A379317.
- A257994 prime, see A002095, A096258, A320628, A331386, A331915, A379304, A379305.
- A330944 nonprime, see A000586, A000607, A076610, A330945.
- A379300 composite, see A023895, A034891, A036497, A302540, A379301.
- A379310 nonsquarefree, see A302478.
- A379311 old prime, see A204389, A320629, A379312-A379315.
Cf. A000720, A013928, A057627, A068361, A070321, A071403, A072284, A112925, A112929, A120327, A377430, A378086.

prix[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Table[Length[Select[prix[n],SquareFreeQ]],{n,100}]

Totally additive with a(prime(k)) = A008966(k).

A243285 Number of integers 1 <= k <= n which are not divisible by the square of their largest noncomposite divisor.

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Jun 02 2014

nonn

a(n) tells how many natural numbers <= n there are which are not divisible by the square of their largest noncomposite divisor.
The largest noncomposite divisor of 1 is 1 itself, and 1 is divisible by 1^2, thus 1 is not included in the count, and a(1)=0.
The "largest noncomposite divisor" for any integer > 1 means the same thing as the largest prime divisor, and thus we are counting the terms of A102750 (Numbers n such that square of largest prime dividing n does not divide n).
Thus this is the partial sums of the characteric function for A102750.

			For n = 9, there are numbers 2, 3, 5, 6 and 7 which are not divisible by the square of their largest prime factor, while 1 is excluded (no prime factors) and 4 and 8 are divisible both by 2^2 and 9 is divisible by 3^2. Thus a(9) = 5.

Antti Karttunen, Table of n, a(n) for n = 1..10000

Cf. A243282, A243283, A102750, A070003, A013928, A057627.

ndsQ[n_]:=Mod[n,Max[Select[Divisors[n],!CompositeQ[#]&]]^2]!=0; Accumulate[Table[If[ ndsQ[n],1,0],{n,80}]] (* Harvey P. Dale, Oct 14 2023 *)

from sympy import primefactors
def a243285(n): return 0 if n==1 else sum([1 for k in range(2, n + 1) if k%(primefactors(k)[-1]**2)!=0]) # Indranil Ghosh, Jun 15 2017

Scheme
```
(define (A243285 n) (- n (A243283 n)))
```

a(n) = n - A243283(n).

For all n, a(A102750(n)) = n, thus this sequence works also as an inverse function for the injection A102750.

A070548 a(n) = Cardinality{ k in range 1 <= k <= n such that Moebius(k) = 1 }.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 5, 5, 5, 5, 5, 5, 6, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 9, 10, 11, 11, 11, 12, 13, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 15, 15, 15, 15, 16, 16, 17, 18, 18, 18, 18, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 21, 22, 22, 22, 23, 23, 23, 23

Offset: 1

Benoit Cloitre, May 02 2002

Moebius(k)=1 iff k is the product of an even number of distinct primes (cf. A008683). See A057627 for Moebius(k)=0.

There was an old comment here that said a(n) was equal to A072613(n) + 1, but this is false (e.g., at n=210). - N. J. A. Sloane, Sep 10 2008

N. J. A. Sloane, Table of n, a(n) for n = 1..10000
Ed Pegg Jr., The Möbius Function (and squarefree numbers), Math Games, November 3, 2003.
Eric Weisstein's World of Mathematics, Mertens Conjecture.

Cf. A008683, A002321, A013928, A059956, A070549.

with(numtheory); M:=10000; c:=0; for n from 1 to M do if mobius(n) = 1 then c:=c+1; fi; lprint(n,c); od; # N. J. A. Sloane, Sep 14 2008

a[n_] := If[MoebiusMu[n] == 1, 1, 0]; Accumulate@ Array[a, 100] (* Amiram Eldar, Oct 01 2023 *)

for(n=1,150,print1(sum(i=1,n,if(moebius(i)-1,0,1)),","))

Asymptotics: Let N(i) = number of k in the range [1,n] with mu(k) = i, for i = 0, 1, -1. Then we know N(1) + N(-1) ~ 6n/Pi^2 (see A059956). Also, assuming the Riemann hypothesis, | N(1) - N(-1) | < n^(1/2 + epsilon) (see the Mathworld Mertens Conjecture link). Hence a(n) = N(1) ~ 3n/Pi^2 + smaller order terms. - Stefan Steinerberger, Sep 10 2008
a(n) = (1/2)*Sum_{i=1..n} (mu(i)^2 + mu(i)) = (1/2)*(A013928(n+1) + A002321(n)). - Ridouane Oudra, Oct 19 2019
From Amiram Eldar, Oct 01 2023: (Start)
a(n) = A013928(n+1) - A070549(n).
a(n) = A070549(n) + A002321(n). (End)

A070549 a(n) = Cardinality{ k in range 1 <= k <= n such that Moebius(k) = -1 }.

Original entry on oeis.org

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

Offset: 1

Benoit Cloitre, May 02 2002

mu(k)=-1 if k is the product of an odd number of distinct primes. See A057627 for mu(k)=0.

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

Cf. A008683, A057627.
Partial sums of A252233.
Cf. A002321, A013928, A030059, A070548, A104141.

ListTools:-PartialSums([seq(-min(numtheory:-mobius(n),0),n=1..100)]); # Robert Israel, Jan 08 2018

a[n_]:=Sum[Boole[MoebiusMu[k]==-1],{k,n}]; Array[a,78] (* Stefano Spezia, Jan 30 2023 *)

for(n=1,150,print1(sum(i=1,n,if(moebius(i)+1,0,1)),","))

From Amiram Eldar, Oct 01 2023: (Start)
a(n) = (A013928(n+1) - A002321(n))/2.
a(n) = A013928(n+1) - A070548(n).
a(n) = A070548(n) - A002321(n).
a(n) ~ (3/Pi^2) * n. (End)

A243283 One more than the partial sums of the characteristic function of A070003.

Original entry on oeis.org

1, 1, 1, 2, 2, 2, 2, 3, 4, 4, 4, 4, 4, 4, 4, 5, 5, 6, 6, 6, 6, 6, 6, 6, 7, 7, 8, 8, 8, 8, 8, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 15, 15, 15, 16

Offset: 1

Antti Karttunen, Jun 02 2014

nonn

a(n) tells how many positive integers <= n are divisible by the square of their largest noncomposite divisor. (This definition includes 1 as it is divisible by 1^2.)
a(n) = n - A243285(n).
a(1) = 1 and for all n > 1, a(A070003(n-1)) = n, thus this sequence works as an inverse function for the injection {a(1) = 1, a(n>1) = A070003(n-1)} (a sequence which is the union of {1} and A070003).

Antti Karttunen, Table of n, a(n) for n = 1..10000

One more than A243282.
Differs from A243284 for the first time at n=48. Here a(48)=10.
Cf. A070003, A102354, A243285, A057627.

A243352 If n is k-th squarefree number [i.e., n = A005117(k)], a(n) = 2k-1; otherwise, when n is k-th nonsquarefree number [i.e., n = A013929(k)], a(n) = 2k.

Original entry on oeis.org

1, 3, 5, 2, 7, 9, 11, 4, 6, 13, 15, 8, 17, 19, 21, 10, 23, 12, 25, 14, 27, 29, 31, 16, 18, 33, 20, 22, 35, 37, 39, 24, 41, 43, 45, 26, 47, 49, 51, 28, 53, 55, 57, 30, 32, 59, 61, 34, 36, 38, 63, 40, 65, 42, 67, 44, 69, 71, 73, 46, 75, 77, 48, 50, 79, 81, 83, 52, 85, 87, 89

Offset: 1

Antti Karttunen, Jun 04 2014

Odd numbers occur (in order) at the positions given by squarefree numbers, A005117, and even numbers occur (in order) at the positions given by their complement, nonsquarefree numbers, A013929.

Antti Karttunen, Table of n, a(n) for n = 1..10001
Index entries for sequences that are permutations of the natural numbers

Inverse: A088610. Cf. A243343, A072062.

(define (A243352 n) (if (zero? (A008966 n)) (* 2 (A057627 n)) (+ (* 2 (A013928 n)) 1)))

If mu(n) = 0, a(n) = 2*A057627(n), otherwise, a(n) = 1 + 2 * A013928(n). [Here mu is Moebius mu-function, A008683, which is zero only when n is a nonsquarefree number, one of the numbers in A013929].

For all n, A000035(a(n)) = A008966(n) = A008683(n)^2, or equally, a(n) = mu(n) modulo 2.

A305980 Filter sequence for a(Squarefree numbers > 1) = constant sequences.

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Jul 02 2018

nonn

For all i, j: A305800(i) = A305800(j) => a(i) = a(j).

Antti Karttunen, Table of n, a(n) for n = 1..100000

Cf. A005117, A008966, A057627, A305800.

up_to = 100000;
partialsums(f,up_to) = { my(v = vector(up_to), s=0); for(i=1,up_to,s += f(i); v[i] = s); (v); }
v057627 = partialsums(x -> !issquarefree(x),up_to);
A057627(n) = v057627[n];
A305980(n) = if(1==n,n,if(issquarefree(n),2,2+A057627(n)));

a(1) = 1; for n > 1, if A008966(n) = 1 [when n is in A005117], then a(n) = 2, otherwise a(n) = 2+A057627(n).

A081239 #{(i,j): mu(i)*mu(j) = 0, 1<=i,j<=n}, where mu=A008683 (Moebius function).

Original entry on oeis.org

0, 0, 0, 7, 9, 11, 13, 28, 45, 51, 57, 80, 88, 96, 104, 135, 145, 180, 192, 231, 245, 259, 273, 320, 369, 387, 440, 495, 517, 539, 561, 624, 648, 672, 696, 767, 793, 819, 845, 924, 952, 980, 1008, 1095, 1184, 1216, 1248, 1343, 1440, 1539, 1577, 1680, 1720

Offset: 1

Reinhard Zumkeller, Mar 11 2003

nonn

A081238(n) + a(n) + A081240(n) = n^2;

a(n) = a(n-1) + 2*n + 1 iff mu(n) = 0.

			n mu(n) ... n: 1 2 3 4 5 6 7 8
- ------ .... |----------------
1 .. +1 ..... | + - - 0 - + - 0
2 .. -1 ..... | - + + 0 + - + 0
3 .. -1 ..... | - + + 0 + - + 0
4 ... 0 ..... | 0 0 0 0 0 0 0 0
5 .. -1 ..... | - + + 0 + - + 0 a(8)=28, as there are
6 .. +1 ..... | + - - 0 - + - 0 28 '0's in the 8x8-square
7 .. -1 ..... | - + + 0 + - + 0
8 ... 0 ..... | 0 0 0 0 0 0 0 0.

Reinhard Zumkeller, Table of n, a(n) for n = 1..500

Cf. A057627.

a081239 n = length [() | u <- [1..n], v <- [1..n],
                         a008683 u * a008683 v == 0]
-- Reinhard Zumkeller, Aug 03 2012

a(n) = n^2 - A013928(n+1)^2. - Vladeta Jovovic, Mar 12 2003

A088609 a(1) = 1, a(n) is the smallest squarefree number not included earlier if n is not squarefree, else n is the smallest nonsquarefree number.

Original entry on oeis.org

1, 4, 8, 2, 9, 12, 16, 3, 5, 18, 20, 6, 24, 25, 27, 7, 28, 10, 32, 11, 36, 40, 44, 13, 14, 45, 15, 17, 48, 49, 50, 19, 52, 54, 56, 21, 60, 63, 64, 22, 68, 72, 75, 23, 26, 76, 80, 29, 30, 31, 81, 33, 84, 34, 88, 35, 90, 92, 96, 37, 98, 99, 38, 39, 100, 104, 108, 41, 112, 116

Offset: 1

Amarnath Murthy, Oct 16 2003

nonn

From Antti Karttunen, Jun 04 2014: (Start)
This is a self-inverse permutation (involution) of natural numbers.
After 1, nonsquarefree numbers occur (in monotonic order) at the positions given by squarefree numbers, A005117, and squarefree numbers occur (in monotonic order) at the positions given by their complement, nonsquarefree numbers, A013929.
(End)

Antti Karttunen, Table of n, a(n) for n = 1..10001
Index entries for sequences that are permutations of the natural numbers

Cf. A026239, A088610-A243352, A243347.

From Antti Karttunen, Jun 04 2014: (Start)
a(1), and for n>1, if mu(n) = 0, a(n) = A005117(1+A057627(n)), otherwise, a(n) =  A013929(A013928(n)). [Here mu is Moebius mu-function, A008683, which is zero only when n is a nonsquarefree number, one of the numbers in A013929].
For all n > 1, A008966(a(n)) = 1 - A008966(n), or equally, mu(a(n)) + 1 = mu(n) modulo 2. [A property shared with A243347].
(End)

More terms from Ray Chandler, Oct 18 2003

A158819 a(n) = (number of squarefree numbers <= n) minus round(n/zeta(2)).

Original entry on oeis.org

0, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 2, 1, 2, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2, 2, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 2, 1, 2, 2, 1, 1, 1, 2, 2, 1, 1, 1, 2, 1, 1, 2, 2, 2, 2, 1, 2, 1, 1, 2, 2, 2, 2, 1, 1, 0, 1, 1, 1, 1, 1

Offset: 1

Daniel Forgues, Mar 27 2009

sign

Race between the number of squarefree numbers and round(n/zeta(2)).

First term < 0: a(172) = -1.

G. H. Hardy and S. Ramanujan, The normal number of prime factors of a number n, Q. J. Math., 48 (1917), pp. 76-92.
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Fifth edition, Clarendon Press, 1979, pp. 269-270.

Daniel Forgues, Table of n, a(n) for n=1..100000
Andrew Granville, ABC allows us to count squarefrees, International Mathematics Research Notices, Vol. 1998, No. 19 (1998), pp. 991-1109; alternative link.

Cf. A008966 (1 if n is squarefree, else 0).
Cf. A013928 (number of squarefree numbers < n).
Cf. A100112 (if n is the k-th squarefree number then k else 0).
Cf. A057627 (number of nonsquarefree numbers not exceeding n).
Cf. A005117 (squarefree numbers).
Cf. A013929 (nonsquarefree numbers).
Cf. A013661 (zeta(2)).

seq[lim_] := Accumulate[Boole[SquareFreeQ /@ Range[lim]]] - Round[Range[lim]/Zeta[2]]; seq[105] (* Amiram Eldar, Jan 20 2025 *)

Since zeta(2) = Sum_{i>=1} 1/(i^2) = (Pi^2)/6, we get:
a(n) = A013928(n+1) - n/Sum_{i>=1} 1/(i^2) = O(sqrt(n));
a(n) = A013928(n+1) - 6*n/(Pi^2) = O(sqrt(n)).

cp's OEIS Frontend

A379306 Number of squarefree prime indices of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A243285 Number of integers 1 <= k <= n which are not divisible by the square of their largest noncomposite divisor.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Scheme

Formula

A070548 a(n) = Cardinality{ k in range 1 <= k <= n such that Moebius(k) = 1 }.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A070549 a(n) = Cardinality{ k in range 1 <= k <= n such that Moebius(k) = -1 }.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A243283 One more than the partial sums of the characteristic function of A070003.

Views

Author

Keywords

Comments

Links

Crossrefs

A243352 If n is k-th squarefree number [i.e., n = A005117(k)], a(n) = 2k-1; otherwise, when n is k-th nonsquarefree number [i.e., n = A013929(k)], a(n) = 2k.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Scheme

Formula

A305980 Filter sequence for a(Squarefree numbers > 1) = constant sequences.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A081239 #{(i,j): mu(i)*mu(j) = 0, 1<=i,j<=n}, where mu=A008683 (Moebius function).

Views

Author

Keywords

Comments