cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

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

This page as a plain text file.
%I A078342 #19 Nov 08 2016 00:49:11
%S A078342 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 A078342 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 A078342 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 A078342 Number of positive integers less than n that are coprime to all primes less than or equal to the square root of n.
%H A078342 Robert Israel, <a href="/A078342/b078342.txt">Table of n, a(n) for n = 1..10000</a>
%F A078342 a(n) = pi(n-1) - pi(sqrt(n)) + 1 for n > 1.
%e A078342 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 A078342 0, seq(numtheory:-pi(n-1) - numtheory:-pi(floor(sqrt(n))) + 1, n=2..100);
%t A078342 a[1]=0; a[n_] := PrimePi[n-1]-PrimePi[Sqrt[n]]+1
%o A078342 (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 A078342 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 A078342 for (i=1,500,print1(newphi(i)",")) \\ _Dean Hickerson_ Nov 24 2002
%o A078342 (PARI) a(n)=if(n>1, primepi(n-1) - primepi(sqrtint(n)) + 1, 0) \\ _Charles R Greathouse IV_, Oct 31 2016
%o A078342 (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 A078342 Cf. A000196, A000720, A056811.
%K A078342 nonn
%O A078342 1,3
%A A078342 _Jon Perry_, Nov 22 2002