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

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

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 (2022) Vol. 22, #A47, see p. 8.

Formula

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

Example

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

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

Prog

(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

Crossrefs

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

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

Cf. A080359, A080360, A080362.

Sequence in context: A316112 A317994 A128428 * A357328 A333749 A238949

Adjacent sequences: A056168 A056169 A056170 * A056172 A056173 A056174

Keyword

nonn,easy

Author

Labos Elemer, Jul 27 2000

Extensions

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

Status

approved