|
%I #19 Nov 08 2016 00:49:11
%S 0,1,2,2,2,3,3,4,3,3,3,4,4,5,5,5,5,6,6,7,7,7,7,8,7,7,7,7,7,8,8,9,9,9,
%T 9,9,9,10,10,10,10,11,11,12,12,12,12,13,12,12,12,12,12,13,13,13,13,13,
%U 13,14,14,15,15,15,15,15,15,16,16,16,16,17,17,18,18,18,18,18,18,19,19,19
%N Number of positive integers less than n that are coprime to all primes less than or equal to the square root of n.
%H Robert Israel, <a href="/A078342/b078342.txt">Table of n, a(n) for n = 1..10000</a>
%F a(n) = pi(n-1) - pi(sqrt(n)) + 1 for n > 1.
%e a(8)=4 as sqrt(8)=~2.8 and from 1,2,3,4,5,6,7, only 1,3,5,7 are coprime to 2.
%p 0, seq(numtheory:-pi(n-1) - numtheory:-pi(floor(sqrt(n))) + 1, n=2..100);
%t a[1]=0; a[n_] := PrimePi[n-1]-PrimePi[Sqrt[n]]+1
%o (PARI) sqp(n)=local(sn,v,p,vc); sn=sqrt(n); v=vector(floor(sn)); p=2; v[1]=2; vc=2; while (nextprime(p+1)<=sn,p=nextprime(p+1); v[vc]=p; vc++); vecextract(v,concat("1..",vc-1));
%o newphi(n)=local(v,vl,fl,np); if(n==3, return(2)); v=sqp(n); vl=length(v); np=0; for (s=1,n-1,fl=false; for (r=1,vl,if (gcd(s,v[r])>1,fl=true; break)); if (fl==false,np++)); np
%o for (i=1,500,print1(newphi(i)",")) \\ _Dean Hickerson_ Nov 24 2002
%o (PARI) a(n)=if(n>1, primepi(n-1) - primepi(sqrtint(n)) + 1, 0) \\ _Charles R Greathouse IV_, Oct 31 2016
%o (PARI) first(n)=my(v=vector(n),s,p=2,sq=4); forprime(q=3,n, s++; print("q = "q", s++ = "s); for(k=p,q-1, if(k==sq, sq=nextprime(sqrtint(sq)+1)^2; s--; print("k = "k", s-- = "s)); v[k]=s); p=q); v \\ _Charles R Greathouse IV_, Nov 08 2016
%Y Cf. A000196, A000720, A056811.
%K nonn
%O 1,3
%A _Jon Perry_, Nov 22 2002
|
