A056171 a(n) = pi(n) - pi(floor(n/2)), where pi is A000720.

0, 1, 2, 1, 2, 1, 2, 2, 2, 1, 2, 2, 3, 2, 2, 2, 3, 3, 4, 4, 4, 3, 4, 4, 4, 3, 3, 3, 4, 4, 5, 5, 5, 4, 4, 4, 5, 4, 4, 4, 5, 5, 6, 6, 6, 5, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 6, 7, 7, 8, 7, 7, 7, 7, 7, 8, 8, 8, 8, 9, 9, 10, 9, 9, 9, 9, 9, 10, 10, 10, 9, 10, 10, 10, 9, 9, 9, 10, 10, 10, 10, 10, 9, 9, 9, 10, 10

Offset: 1

Author

Labos Elemer, Jul 27 2000

Keywords

• nonn
• easy

Comments

Also, the number of unitary prime divisors of n!. A prime divisor of n is unitary iff its exponent is 1 in the prime power factorization of n. In general, gcd(p, n/p) = 1 or p. Here we count the cases when gcd(p, n/p) = 1.

A unitary prime divisor of n! is >= n/2, hence their number is pi(n) - pi(n/2). - Peter Luschny, Mar 13 2011

See also the references and links mentioned in A143227. - Jonathan Sondow, Aug 03 2008

From Robert G. Wilson v, Mar 20 2017: (Start)

First occurrence of k is at n = A080359(k).

The last occurrence of k is at n = A080360(k).

The number of times k appears is A080362(k). (End)

Lev Schnirelmann proved that for every n, a(n) > (1/log_2(n))*(n/3 - 4*sqrt(n)) - 1 - (3/2)*log_2(n). - Arkadiusz Wesolowski, Nov 03 2017

Examples

			10! = 2^8 * 3^2 * 5^2 * 7. The only unitary prime divisor is 7, so a(10) = 1.
		

References

• Paulo Ribenboim, The Little Book of Bigger Primes, Springer-Verlag NY 2004. See p. 214.

Links

• Daniel Forgues, Table of n, a(n) for n=1..100000
• Ethan Berkove and Michael Brilleslyper, Subgraphs of Coprime Graphs on Sets of Consecutive Integers, Integers, Vol. 22 (2022), #A47, see p. 8.

Crossrefs

Cf. A000720, A001221, A034444, A048105, A048656, A048657, A056169, A056172.

Cf. A014085, A060715, A104272, A143223, A143224, A143225, A143226, A143227.

Cf. A080359, A080360, A080362.

Programs

Maple

A056171 := proc(x)
     numtheory[pi](x)-numtheory[pi](floor(x/2)) ;
end proc:
seq(A056171(n),n=1..130) ; # N. J. A. Sloane, Sep 01 2015
A056171 := n -> nops(select(isprime,[$iquo(n,2)+1..n])):
seq(A056171(i),i=1..98); # Peter Luschny, Mar 13 2011

Mathematica

s=0; Table[If[PrimeQ[k], s++]; If[PrimeQ[k/2], s--]; s, {k,100}]
Table[PrimePi[n]-PrimePi[Floor[n/2]],{n,100}] (* Harvey P. Dale, Sep 01 2015 *)

PARI

A056171=n->primepi(n)-primepi(n\2) \\ M. F. Hasler, Dec 31 2016

Python

from sympy import primepi
[primepi(n) - primepi(n//2) for n in range(1,151)] # Indranil Ghosh, Mar 22 2017

Sage

[prime_pi(n)-prime_pi(floor(n/2)) for n in range(1,99)] # Stefano Spezia, Apr 22 2025

Formula

a(n) = A000720(n) - A056172(n). - Robert G. Wilson v, Apr 09 2017

a(n) = A056169(n!). - Amiram Eldar, Jul 24 2024

Extensions

Definition simplified by N. J. A. Sloane, Sep 01 2015