

A048869


Numbers for which reduced residue system contains as many primes as nonprimes.


2



3, 4, 5, 6, 7, 9, 10, 15, 21, 45, 58, 82, 86, 92, 105, 116, 196, 238, 308, 310, 320, 380, 972, 978, 996, 1068, 1368, 5640, 10890
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


COMMENTS

This sequence is finite, since the number of primes < n is ~ n/log(n), but liminf phi(n) / ( n*log(log(n)) ) = exp(gamma), a consequence of Mertens's theorem (see Hardy and Wright's Theory of Numbers). Also, if there exists a further element, it is >700000 (as verified with the enclosed Mathematica code). (Question: is it possible to show that there are no further such elements by using explicit bounds in the Prime Number Theorem and in Mertens's theorem?)  Reiner Martin (reinermartin(AT)hotmail.com), Jan 16 2002
There are no terms larger than 10890; it suffices to check to 52024. [Charles R Greathouse IV, Dec 19 2011]


LINKS

Table of n, a(n) for n=1..29.


EXAMPLE

n=45, phi(45)=24 and the reduced residue system mod 45 contains 12 primes {2,7,11,13,17,19,23,29,31,37,41,43} and 12 nonprimes {1,4,8,14,16,22,26,28,32,34,38,44}.


MATHEMATICA

Select[Range[700000], 2(PrimePi[ # ]  Length[FactorInteger[ # ]]) == EulerPhi[ # ]&]
For[i = 1, i < 100000000000, i++, If[2(PrimePi[i]  Length[FactorInteger[i]]) == EulerPhi[i], Print[i]]];  Sam Handler (sam_5_5_5_0(AT)yahoo.com), Aug 29 2006


PROG

(PARI) p=0; for(n=1, 6e4, if(isprime(n), p++); if(p==eulerphi(n)/2+omega(n), print1(n", "))) \\ Charles R Greathouse IV, Dec 19 2011


CROSSREFS

A000720(n)A001221(n) = A000010(n)  [ A000720(n)A001221(n) ].
Cf. A048597A002110.
Sequence in context: A026438 A026442 A307712 * A039051 A047564 A154536
Adjacent sequences: A048866 A048867 A048868 * A048870 A048871 A048872


KEYWORD

nonn,fini,full


AUTHOR

Labos Elemer


EXTENSIONS

More terms from Sam Handler (sam_5_5_5_0(AT)yahoo.com), Aug 29 2006


STATUS

approved



