A078342 Number of positive integers less than n that are coprime to all primes less than or equal to the square root of n.

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, 9, 9, 9, 10, 10, 10, 10, 11, 11, 12, 12, 12, 12, 13, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 14, 14, 15, 15, 15, 15, 15, 15, 16, 16, 16, 16, 17, 17, 18, 18, 18, 18, 18, 18, 19, 19, 19

Offset: 1

Author

Jon Perry, Nov 22 2002

Keywords

• nonn

Examples

			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.
		

Links

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

Crossrefs

Cf. A000196, A000720, A056811.

Programs

Maple

0, seq(numtheory:-pi(n-1) - numtheory:-pi(floor(sqrt(n))) + 1, n=2..100);

Mathematica

a[1]=0; a[n_] := PrimePi[n-1]-PrimePi[Sqrt[n]]+1

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));
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
for (i=1,500,print1(newphi(i)",")) \\ Dean Hickerson Nov 24 2002

PARI

a(n)=if(n>1, primepi(n-1) - primepi(sqrtint(n)) + 1, 0) \\ Charles R Greathouse IV, Oct 31 2016

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

Formula

a(n) = pi(n-1) - pi(sqrt(n)) + 1 for n > 1.