A234958 -id:A234958 - cp's OEIS frontend

A238574 k-Lehmer numbers: composite integers n such that phi(n) | (n-1)^k.

15, 51, 85, 91, 133, 247, 255, 259, 435, 451, 481, 511, 561, 595, 679, 703, 763, 771, 949, 1105, 1111, 1141, 1261, 1285, 1351, 1387, 1417, 1615, 1695, 1729, 1843, 1891, 2047, 2071, 2091, 2119, 2431, 2465, 2509, 2701, 2761, 2821, 2955, 3031, 3097, 3145, 3277

Offset: 1

José María Grau Ribas, Mar 01 2014

nonn

Composite numbers in A187731.

J. M. Grau and A. M. Oller-Marcén showed that all terms of this sequence are terms of A003277 (cyclic numbers) and this sequence contains all terms of A002997 (Carmichael numbers). - Tomohiro Yamada, Sep 28 2020

			2^3*3^2 = 72 = phi(91) divides (91-1)^3 = (2*3^2*5)^3 implies 91 is a 3-Lehmer number.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
J. M. Grau and A. M. Oller-Marcén, On k-Lehmer numbers, Integers, 12(2012), #A37.
Max Lewis and Victor Scharaschkin, k-Lehmer and k-Carmichael Numbers, Integers, 16 (2016), #A80.
Nathan McNew, Radically weakening the Lehmer and Carmichael conditions, arXiv:1210.2001 [math.NT], 2012; International Journal of Number Theory 9 (2013), 1215-1224.
Nathan McNew, Multiplicative problems in combinatorial number theory, Thesis, 2015.
Nathan McNew and Thomas Wright, Infinitude of k-Lehmer numbers which are not Carmichael, Int. J. Number Theory V.12(7), pp. 1863-1869, (2016).
Giovanni Resta, k-Lehmer numbers.

Cf. A187731 (numbers n such that rad(phi(n)) divides n-1).
Cf. A173703 (2-Lehmer numbers; i.e., phi(n) divides (n-1)^2).
Cf. A234936 (smallest composite n-Lehmer number which is not an (n-1)-Lehmer number).
Cf. A207080 (minimum Carmichael number which is not an n-Lehmer number).
Cf. A234958 (number of k-Lehmer numbers up to 10^n).
Cf. A238575 (k-Lehmer numbers with two prime factors).
Cf. A002997, A003277.

rad[n_]:=Times@@Transpose[FactorInteger[n]][[1]]; Select[1+Range[1000], !PrimeQ[#]&&Mod[#-1, rad[EulerPhi[#]]]==0&]

is(n)=my(p=eulerphi(n),g=n); if(isprime(n),return(0),n--); while((g=gcd(p,g))>1, p/=g); p==1 && n \\ Charles R Greathouse IV, Mar 03 2014

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

Original entry on oeis.org

561, 15, 451, 51, 679, 255, 2091, 771, 43435, 3855, 31611, 13107, 272163, 65535, 494211, 196611, 2089011, 983055, 8061051, 3342387, 31580931, 16711935, 126027651, 50529027, 756493591, 252645135, 4446487299, 858993459, 8053383171, 4294967295, 32212942851

Offset: 2

Giovanni Resta, Jan 01 2014

nonn

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.

			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.

Giovanni Resta, Table of n, a(n) for n = 2..36
José María Grau and Antonio M. Oller-Marcén, On k-Lehmer numbers, arXiv:1012.2337 [math.NT], 2010-2012.
José María Grau and Antonio M. Oller-Marcén, On k-Lehmer numbers, Integers, 12(2012), #A37.
Nathan McNew, Radically weakening the Lehmer and Carmichael conditions, arXiv:1210.2001 [math.NT], 2012; International Journal of Number Theory 9 (2013), 1215-1224.

Cf. A187731, A173703, A234958.

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 *)

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

cp's OEIS Frontend

A238574 k-Lehmer numbers: composite integers n such that phi(n) | (n-1)^k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI