login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A039769 Composite integers k such that gcd(phi(k), k - 1) > 1. 5

%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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 20:05 EDT 2024. Contains 371254 sequences. (Running on oeis4.)