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

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

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, 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. A048597-A002110.

Sequence in context: A026442 A334763 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