|
Search: id:A078342
|
|
|
| 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
|
|
| 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; listen)
|
|
|
OFFSET
|
1,3
|
|
|
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.
|
|
MATHEMATICA
|
a[1]=0; a[n_] := PrimePi[n-1]-PrimePi[Sqrt[n]]+1
|
|
PROGRAM
|
(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); 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)", ")) \\ This gives the wrong value for newphi(3). - Dean Hickerson Nov 24 2002
|
|
CROSSREFS
|
Sequence in context: A064822 A104484 A038809 this_sequence A107325 A003050 A070868
Adjacent sequences: A078339 A078340 A078341 this_sequence A078343 A078344 A078345
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Jon Perry (perry(AT)globalnet.co.uk), Nov 22 2002
|
|
|
Search completed in 0.002 seconds
|
