login
Even numbers k such that phi(k) and k-1 are distinct and have a common factor > 1.
8

%I #27 Mar 16 2019 15:15:42

%S 28,52,66,70,76,112,124,130,148,154,172,176,186,190,196,208,232,238,

%T 244,246,268,276,280,286,292,304,310,316,322,344,364,366,370,388,396,

%U 406,412,418,426,430,436,442,448,490,496,506,508,520,532,556,568,574

%N Even numbers k such that phi(k) and k-1 are distinct and have a common factor > 1.

%C Also this sequence is the union of all possible even Fermat pseudoprimes q to some prime base p>q such that q does not divide p-1. Note that all even nonprime divisors of p-1 are the Fermat pseudoprimes to prime base p. E.g. q = {4,6,12,18,28,36} is a set of even Fermat pseudoprimes to prime base p = 37, but only number q = 28 from this set does not divide p-1 = 36. - _Alexander Adamchuk_, Jun 16 2007

%H Robert Israel, <a href="/A039772/b039772.txt">Table of n, a(n) for n = 1..10000</a>

%H Romeo Meštrović, <a href="http://arxiv.org/abs/1305.1867">Generalizations of Carmichael numbers I,</a> arXiv:1305.1867v1 [math.NT], May 04 2013.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/FermatPseudoprime.html">Fermat Pseudoprime</a>

%e phi(28)=12, gcd(12,27)=3.

%p select(t -> igcd(numtheory:-phi(t), t-1)>1, [seq(n,n=2..1000,2)]); # _Robert Israel_, May 15 2017

%t Select[Range[2, 1000, 2], !CoprimeQ[EulerPhi[#], #-1]&] (* _Jean-François Alcover_, Sep 19 2018 *)

%o (PARI) isok(n) = !(n%2) && (gcd(eulerphi(n), n-1) != 1); \\ _Michel Marcus_, Mar 15 2019

%Y Cf. A000010, A049559.

%K nonn,easy

%O 1,1

%A _Olivier Gérard_