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,1

Comments

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

Links

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

Formula

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

Example

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.

Mathematica

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

Prog

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

Crossrefs

Cf. A001221, A000010, A055742, A055743.

Sequence in context: A248963 A221636 A162018 * A103621 A081239 A264814

Adjacent sequences: A055738 A055739 A055740 * A055742 A055743 A055744

Keyword

nonn

Author

Labos Elemer, Jul 11 2000

Status

approved