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

Links

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

Formula

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

Example

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.

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

Prog

(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

Crossrefs

Cf. A000196, A000720, A056811.

Sequence in context: A104484 A038809 A337496 * A177903 A107325 A003050

Adjacent sequences: A078339 A078340 A078341 * A078343 A078344 A078345

Keyword

nonn

Author

Jon Perry, Nov 22 2002

Status

approved