A234936 - OEIS

%I #24 Jan 26 2019 14:27:01

%S 561,15,451,51,679,255,2091,771,43435,3855,31611,13107,272163,65535,

%T 494211,196611,2089011,983055,8061051,3342387,31580931,16711935,

%U 126027651,50529027,756493591,252645135,4446487299,858993459,8053383171,4294967295,32212942851

%N a(n) is the smallest composite n-Lehmer number.

%C A number n is a k-Lehmer number if there exists a k such that phi(n) divides (n-1)^k, but not (n-1)^(k-1). The existence of a composite 1-Lehmer number is deemed improbable.

%H Giovanni Resta, <a href="/A234936/b234936.txt">Table of n, a(n) for n = 2..36</a>

%H José María Grau and Antonio M. Oller-Marcén, <a href="http://arxiv.org/abs/1012.2337">On k-Lehmer numbers</a>, arXiv:1012.2337 [math.NT], 2010-2012.

%H José María Grau and Antonio M. Oller-Marcén, <a href="https://www.emis.de/journals/INTEGERS/papers/m37/m37.Abstract.html">On k-Lehmer numbers</a>, Integers, 12(2012), #A37.

%H Nathan McNew, <a href="http://arxiv.org/abs/1210.2001">Radically weakening the Lehmer and Carmichael conditions</a>, arXiv:1210.2001 [math.NT], 2012; International Journal of Number Theory 9 (2013), 1215-1224.

%e a(3) = 15 because 15 is the smallest n such that phi(n) divides (n-1)^3 and does not divide (n-1)^2, i.e., it is the smallest 3-Lehmer number.

%t a[n_] := a[n] = For[k = 2, True, k++, If[CompositeQ[k], phi = EulerPhi[k]; If[Divisible[(k-1)^n, phi], If[!Divisible[(k-1)^(n-1), phi], Return[k] ]]]]; Table[Print[n, " ", a[n]]; a[n], {n, 2, 20}] (* _Jean-François Alcover_, Jan 26 2019 *)

%o (PARI) a(n) = {x = 2; while (!(!((x-1)^n % eulerphi(x)) && ((x-1)^(n-1) % eulerphi(x))), x++); x;} \\ _Michel Marcus_, Jan 26 2014

%Y Cf. A187731, A173703, A234958.

%K nonn

%O 2,1

%A _Giovanni Resta_, Jan 01 2014