

A039769


Composite integers k such that gcd(phi(k), k  1) > 1.


5



9, 15, 21, 25, 27, 28, 33, 35, 39, 45, 49, 51, 52, 55, 57, 63, 65, 66, 69, 70, 75, 76, 77, 81, 85, 87, 91, 93, 95, 99, 105, 111, 112, 115, 117, 119, 121, 123, 124, 125, 129, 130, 133, 135, 141, 143, 145, 147, 148, 153, 154, 155, 159, 161, 165, 169, 171, 172, 175
(list;
graph;
refs;
listen;
history;
text;
internal format)



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^(n1) = 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(n1, 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), k1) > 1, print1(k, ", "))); \\ Altug Alkan, Sep 21 2018


CROSSREFS

Cf. A000010, A071904, A181780.
Sequence in context: A255763 A079364 A160666 * A270574 A071904 A014076
Adjacent sequences: A039766 A039767 A039768 * A039770 A039771 A039772


KEYWORD

nonn,easy,changed


AUTHOR

Olivier Gérard


EXTENSIONS

Name clarified by Tom Edgar, Apr 05 2015


STATUS

approved



