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
KEYWORD
nonn
AUTHOR
Jon Perry, Nov 22 2002
STATUS
approved