login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A078342 Number of positive integers less than n that are coprime to all primes less than or equal to the square root of n. 1
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 (list; graph; refs; listen; history; text; internal format)
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: A238337 A104484 A038809 * A177903 A107325 A003050

Adjacent sequences:  A078339 A078340 A078341 * A078343 A078344 A078345

KEYWORD

nonn

AUTHOR

Jon Perry, Nov 22 2002

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 17 04:56 EDT 2019. Contains 327119 sequences. (Running on oeis4.)