OFFSET
1,1
COMMENTS
Previous name was: phi(a(n)) and (a(n) - 1) have a common factor but are distinct.
Equivalently, numbers n that are Fermat pseudoprimes to some base b, 1 < b < n. A nonprime number n is a Fermat pseudoprime to base b if b^(n-1) = 1 (mod n). Cf. A181780. - Geoffrey Critzer, Apr 04 2015
A071904, the odd composite numbers, is a subset of this sequence. - Peter Munn, May 15 2017
Lehmer's totient problem can be stated as finding a number in this sequence such that gcd(a(n) - 1, phi(a(n))) = phi(n). By the original definition of this sequence, such a number (if it exists) would not be in this sequence. - Alonso del Arte, Sep 07 2018, clarified Sep 14 2018
LINKS
Robert Israel, Table of n, a(n) for n = 1..10000
EXAMPLE
phi(21) = 12 and gcd(12, 20) = 4 > 1, hence 21 is in the sequence.
phi(22) = 10 but gcd(10, 21) = 1, so 22 is not in the sequence.
MAPLE
select(n -> not isprime(n) and igcd(n-1, numtheory:-phi(n))>1, [$4..1000]); # Robert Israel, Apr 07 2015
MATHEMATICA
Select[Range[250], GCD[EulerPhi[#], # - 1] > 1 && EulerPhi[#] != # - 1 &] (* Geoffrey Critzer, Apr 04 2015 *)
PROG
(PARI) forcomposite(k=1, 1e3, if(gcd(eulerphi(k), k-1) > 1, print1(k, ", "))); \\ Altug Alkan, Sep 21 2018
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
EXTENSIONS
Name clarified by Tom Edgar, Apr 05 2015
STATUS
approved