|
%I #37 Sep 21 2018 03:33:02
%S 9,15,21,25,27,28,33,35,39,45,49,51,52,55,57,63,65,66,69,70,75,76,77,
%T 81,85,87,91,93,95,99,105,111,112,115,117,119,121,123,124,125,129,130,
%U 133,135,141,143,145,147,148,153,154,155,159,161,165,169,171,172,175
%N Composite integers k such that gcd(phi(k), k - 1) > 1.
%C Previous name was: phi(a(n)) and (a(n) - 1) have a common factor but are distinct.
%C 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
%C A071904, the odd composite numbers, is a subset of this sequence. - _Peter Munn_, May 15 2017
%C 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
%H Robert Israel, <a href="/A039769/b039769.txt">Table of n, a(n) for n = 1..10000</a>
%e phi(21) = 12 and gcd(12, 20) = 4 > 1, hence 21 is in the sequence.
%e phi(22) = 10 but gcd(10, 21) = 1, so 22 is not in the sequence.
%p select(n -> not isprime(n) and igcd(n-1, numtheory:-phi(n))>1, [$4..1000]); #_Robert Israel_, Apr 07 2015
%t Select[Range[250], GCD[EulerPhi[#], # - 1] > 1 && EulerPhi[#] != # - 1 &] (* _Geoffrey Critzer_, Apr 04 2015 *)
%o (PARI) forcomposite(k=1, 1e3, if(gcd(eulerphi(k), k-1) > 1, print1(k, ", "))); \\ _Altug Alkan_, Sep 21 2018
%Y Cf. A000010, A071904, A181780.
%K nonn,easy
%O 1,1
%A _Olivier Gérard_
%E Name clarified by _Tom Edgar_, Apr 05 2015
|
