A055741 Phi(n) has more distinct prime factors than n.

7, 9, 11, 13, 19, 23, 25, 27, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 62, 67, 71, 73, 77, 79, 81, 83, 86, 89, 93, 97, 98, 99, 101, 103, 107, 109, 113, 121, 122, 124, 125, 127, 129, 131, 134, 137, 139, 142, 143, 147, 149, 151, 155, 157, 158, 161, 163, 167, 169, 172

Offset: 1

Author

Labos Elemer, Jul 11 2000

Keywords

• nonn

Comments

Conjecture: a(n) ~ n. - Charles R Greathouse IV, Mar 04 2017

Examples

			All primes except Fermat primes are included. Also proper prime powers are included, such as 289 because phi(289) = 17*16 = 272 with 2 prime divisors. Besides many composites are included like 998 = 2*499 because phi(998) = 498 = 2*3*83 with 3 > 2 prime factors.
		

Links

• Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A001221, A000010, A055742, A055743.

Programs

Mathematica

Select[Range[100], PrimeNu[EulerPhi[#]] > PrimeNu[#] &] (* G. C. Greubel, May 13 2017 *)

PARI

is(n)=my(f=factor(n)); omega(eulerphi(f)) > #f~ \\ Charles R Greathouse IV, Mar 04 2017

Formula

A001221(A000010(n)) > A001221(n)