login
Number of composite k-Lehmer numbers up to 10^n.
2

%I #7 Jan 02 2014 18:08:02

%S 0,4,19,103,422,1559,5645,19329,64040,207637,663845,2103055

%N Number of composite k-Lehmer numbers up to 10^n.

%C A number n is a k-Lehmer number if there exist a k such that phi(n) divides (n-1)^k.

%C The values of a(10) and a(11) computed by N. McNew in the linked paper are smaller than mine. I provide a link to my full list so that it could be independently checked.

%H José María Grau and Antonio M. Oller-Marcén, <a href="http://arxiv.org/abs/1012.2337">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> International Journal of Number Theory 9 (2013), 1215-1224.

%H Giovanni Resta, <a href="http://www.numbersaplenty.com/set/Lehmer_number/">k-Lehmer numbers</a> composite k-Lehmer numbers up to 10^12.

%e There are 4 k-Lehmer numbers up to 10^2, namely 15, 51, 85, and 91, so a(2) = 4.

%t kLQ[n_] := n > 1 && ! PrimeQ[n] && Mod[n-1, Times @@ First /@ FactorInteger@ EulerPhi@n] == 0; Table[Length@ Select[Range[2, 10^k], kLQ], {k, 6}]

%Y Cf. A187731, A173703, A234936.

%K nonn

%O 1,2

%A _Giovanni Resta_, Jan 01 2014