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

Author

Labos Elemer

Keywords

• nonn
• fini
• full

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]

Examples

			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}.
		

Crossrefs

A000720(n)-A001221(n) = A000010(n) - [ A000720(n)-A001221(n) ].

Cf. A048597-A002110.

Programs

Mathematica

Select[Range[700000], 2(PrimePi[ # ] - Length[FactorInteger[ # ]]) == EulerPhi[ # ]&]
For[i = 1, i < 20000, 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 *)

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

Extensions

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