%I #70 Jul 24 2024 21:09:42
%S 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,
%T 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,
%U 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
%N a(n) = pi(n) - pi(floor(n/2)), where pi is A000720.
%C 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.
%C A unitary prime divisor of n! is >= n/2, hence their number is pi(n) - pi(n/2). - _Peter Luschny_, Mar 13 2011
%C See also the references and links mentioned in A143227. - _Jonathan Sondow_, Aug 03 2008
%C From _Robert G. Wilson v_, Mar 20 2017: (Start)
%C First occurrence of k is at n = A080359(k).
%C The last occurrence of k is at n = A080360(k).
%C The number of times k appears is A080362(k). (End)
%C 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
%H Daniel Forgues, <a href="/A056171/b056171.txt">Table of n, a(n) for n=1..100000</a>
%H Ethan Berkove and Michael Brilleslyper, <a href="http://math.colgate.edu/~integers/w47/w47.pdf">Subgraphs of Coprime Graphs on Sets of Consecutive Integers</a>, Integers, Vol. 22 (2022), #A47, see p. 8.
%F a(n) = A000720(n) - A056172(n). - _Robert G. Wilson v_, Apr 09 2017
%F a(n) = A056169(n!). - _Amiram Eldar_, Jul 24 2024
%e 10! = 2^8 * 3^2 * 5^2 * 7. The only unitary prime divisor is 7, so a(10) = 1.
%p A056171 := proc(x)
%p numtheory[pi](x)-numtheory[pi](floor(x/2)) ;
%p end proc:
%p seq(A056171(n),n=1..130) ; # _N. J. A. Sloane_, Sep 01 2015
%p A056171 := n -> nops(select(isprime,[$iquo(n,2)+1..n])):
%p seq(A056171(i),i=1..98); # _Peter Luschny_, Mar 13 2011
%t s=0; Table[If[PrimeQ[k], s++]; If[PrimeQ[k/2], s--]; s, {k,100}]
%t Table[PrimePi[n]-PrimePi[Floor[n/2]],{n,100}] (* _Harvey P. Dale_, Sep 01 2015 *)
%o (PARI) A056171=n->primepi(n)-primepi(n\2) \\ _M. F. Hasler_, Dec 31 2016
%o (Python)
%o from sympy import primepi
%o [primepi(n) - primepi(n//2) for n in range(1,151)] # _Indranil Ghosh_, Mar 22 2017
%Y Cf. A000720, A001221, A034444, A048105, A048656, A048657, A056169, A056172.
%Y Cf. A014085, A060715, A104272, A143223, A143224, A143225, A143226, A143227.
%Y Cf. A080359, A080360, A080362.
%K nonn,easy
%O 1,3
%A _Labos Elemer_, Jul 27 2000
%E Definition simplified by _N. J. A. Sloane_, Sep 01 2015