A187731 -id:A187731 - 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

A238575 k-Lehmer numbers with two prime factors.

Original entry on oeis.org

15, 51, 85, 91, 133, 247, 259, 451, 481, 511, 679, 703, 763, 771, 949, 1111, 1141, 1261, 1285, 1351, 1387, 1417, 1843, 1891, 2047, 2071, 2119, 2509, 2701, 2761, 3031, 3097, 3277, 3409, 3589, 3667, 4033, 4039, 4141, 4369, 4411, 4681, 5383, 5461, 5611, 5629

Offset: 1

José María Grau Ribas, Mar 01 2014

nonn

The first terms which are == 0 (mod 3) are 15, 51, 771, 196611, which are equal to 3*(5, 17, 257, 65537) = 3*(2^2+1, 2^4+1, 2^8+1, 2^16+1), i.e., 3 times the Fermat primes > 3. No other exceptions below 10^9. - Giovanni Resta

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A187731, A238574.

rad[n_] := Times @@ Transpose[FactorInteger[n]][[1]]; Select[1 + \
Range[10000], Length[FactorInteger[#]] == 2 && Mod[# - 1,
   rad[EulerPhi[#]]] == 0 &]

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

Original entry on oeis.org

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

Offset: 1

Giovanni Resta, Jan 01 2014

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

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.

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

José María Grau and Antonio M. Oller-Marcén, On k-Lehmer numbers, arXiv:1012.2337 [math.NT], 2010-2012; 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.
Giovanni Resta, k-Lehmer numbers composite k-Lehmer numbers up to 10^12.

Cf. A187731, A173703, A234936.

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}]

A333314 Composite non-Carmichael numbers k such that rad(phi(k)) divides k-1, where rad(k) is the squarefree kernel of k (A007947) and phi is the Euler totient function (A000010).

Original entry on oeis.org

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

Offset: 1

Amiram Eldar, Mar 14 2020

nonn

McNew and Wright proved that this sequence is infinite.

			15 = 3 * 5 is a term since it is composite and not a Carmichael number, and rad(phi(15)) = rad(8) = 2 divides 15 - 1 = 14.

Amiram Eldar, Table of n, a(n) for n = 1..10000
Nathan McNew and Thomas Wright, Infinitude of k-Lehmer numbers which are not Carmichael, International Journal of Number Theory, Vol. 12, No. 7 (2016), pp. 1863-1869; preprint, arXiv:1508.05547 [math.NT], 2015.

Complement of the primes and Carmichael numbers (union of A000010 and A002997) with respect to A187731.
Complement of A002997 with respect to A238574.
Cf. A007947, A238575.

rad[n_] := Times @@ (First@# & /@ FactorInteger[n]); Select[Range[4000], Divisible[#-1, rad[EulerPhi[#]]] && !Divisible[#-1, CarmichaelLambda[#]] &]

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A238575 k-Lehmer numbers with two prime factors.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A333314 Composite non-Carmichael numbers k such that rad(phi(k)) divides k-1, where rad(k) is the squarefree kernel of k (A007947) and phi is the Euler totient function (A000010).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica