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

A207080 The smallest Carmichael number k such that phi(k) does not divide (k-1)^n, where phi is the Euler totient function.

Original entry on oeis.org

561, 2821, 838201, 41471521, 45496270561, 776388344641, 344361421401361, 375097930710820681, 330019822807208371201, 4971170854788923506051

Offset: 1

José María Grau Ribas, Feb 15 2012

Conjecture: phi(a(n)) divides (a(n)-1)^(n+1).

a(10) <= 9645020063586019926451. - Daniel Suteu, Dec 25 2020

Claude Goutier, Compressed text file carm10e22.gz containing all the Carmichael numbers up to 10^22.
José María Grau and Antonio M. Oller-Marcén, On k-Lehmer numbers, Integers, 12 (2012), #A37; alternative link; arXiv preprint, arXiv:1012.2337 [math.NT], 2010-2012.
Nathan McNew, Radically weakening the Lehmer and Carmichael conditions, International Journal of Number Theory, Vol. 9, No. 5 (2013), pp. 1215-1224; arXiv preprint, arXiv:1210.2001 [math.NT], 2012.

Cf. A000010, A002997 (Carmichael numbers), A173703.

is_c(n) = { my(f); bittest(n, 0) && !for(i=1, #f=factor(n)~, (f[2, i]==1 && n%(f[1, i]-1)==1)||return) && #f>1; }
isok(k, n) = ((k-1)^n % eulerphi(k)) != 0;
a(n) = my(k=1); while (!(is_c(k) && isok(k,n)), k++); k; \\ Michel Marcus, Dec 25 2020

a(7)-a(9) from Richard Pinch, Feb 18 2012

a(10) calculated using data from Claude Goutier and added by Amiram Eldar, Apr 20 2024

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

A337316 Composite numbers k such that phi(k) divides d*(k - 1) for some squarefree divisor d of k - 1.

Original entry on oeis.org

1729, 12801, 247105, 1224721, 2704801, 5079361, 8355841, 26906881, 30240001, 34479361, 36426241, 45318561, 48188161, 49871361, 61485601, 107714881, 170947105, 178312321, 193708801, 393760321, 446569201, 475683841, 740376001, 781347841, 878169601, 987275521, 1022304361

Offset: 1

Tomohiro Yamada, Sep 28 2020

nonn

All terms of this sequence are terms of A173703 (2-Lehmer numbers) and all Lehmer numbers (if there are any) are contained in this sequence.

			phi(247105) = 194688 divides 2 * 13 * 247104.

Max Alekseyev, Table of n, a(n) for n = 1..114

Cf. A173703 (2-Lehmer numbers), A238574 (k-Lehmer numbers for some k).

Cf. A000010 (phi), A005117 (squarefree numbers).

divQ[n_] := AnyTrue[Select[Divisors[n - 1], SquareFreeQ]*(n - 1), Divisible[#, EulerPhi[n]] &]; Select[Range[250000], CompositeQ[#] && divQ[#] &] (* Amiram Eldar, Oct 14 2020 *)

is(n)={my(s=denominator((n-1)/eulerphi(n))); !isprime(n) && issquarefree(s) && ((n-1)%s==0) && n>1}
{ forcomposite(n=1, 2^28, if(is(n), print1(n, ", "))) }

More terms from Amiram Eldar, Oct 14 2020

A277366 Composite numbers k such that phi(k)*lambda(k) divides (k-1)^2, where phi(k) = A000010(k) and lambda(k) = A002322(k).

Original entry on oeis.org

1729, 670033, 6840001, 83099521, 193708801, 321197185, 367804801, 484662529, 1752710401, 2320690177, 5064928705, 12820178449, 32220147601, 257124585601, 270177600001, 301036080385, 7043394657601, 13237329899521, 14276860416001, 85661522006401, 119377939968001

Offset: 1

Thomas Ordowski, Oct 11 2016

nonn

Are there infinitely many such numbers?

Such k must be a Carmichael number since phi(k)*lambda(k) = m*lambda(k)^2 for some integer m. - Nathan McNew, Oct 11 2016

Amiram Eldar, Table of n, a(n) for n = 1..115 (terms below 10^22, calculated using data from Claude Goutier)
Claude Goutier, Compressed text file carm10e22.gz containing all the Carmichael numbers up to 10^22.
Index entries for sequences related to Carmichael numbers.

Subsequence of A002997 and of A173703.

Cf. A000010, A002322, A002997, A173703.

Select[Range[10^8], CompositeQ[#] && Divisible[(# - 1)^2, EulerPhi[#] * CarmichaelLambda[#]] &] (* Amiram Eldar, Feb 02 2019 *)

lista(nn) = forcomposite(n=4, nn, if (((n-1)^2 % (eulerphi(n)*lcm(znstar(n)[2]))) == 0, print1(n, ", "));); \\ Michel Marcus, Oct 11 2016

is(n,f=factor(n))=(n-1)^2%(eulerphi(f)*lcm(znstar(f)[2])) == 0 && !isprime(n) && n>1 \\ Charles R Greathouse IV, Oct 11 2016

a(2)-a(3) from Michel Marcus, Oct 11 2016
a(4)-a(8) from Charles R Greathouse IV, Oct 11 2016
a(9)-a(13) from David A. Corneth, Oct 11 2016
More terms from Amiram Eldar, Feb 02 2019

A306338 Carmichael numbers k such that phi(k) divides (k-1)*lambda(k).

Original entry on oeis.org

561, 1105, 1729, 2465, 6601, 15841, 41041, 46657, 52633, 75361, 115921, 334153, 340561, 658801, 670033, 2455921, 2704801, 4903921, 5049001, 6049681, 6840001, 8355841, 9439201, 9582145, 9613297, 10402561, 11119105, 11205601, 11972017, 14469841, 15888313, 16778881

Offset: 1

Amiram Eldar and Thomas Ordowski, Feb 08 2019

nonn

Carmichael numbers k such that A034380(k) divides k-1.
A proper subset of Carmichael numbers in A173703.
The number of terms below 10^k for k=1,2,...,18 is 0, 0, 1, 5, 10, 15, 25, 56, 101, 184, 310, 508, 814, 1265, 1964, 2990, 4486, 6704. Cf. A055553.
Composite numbers k such that lcm(lambda(k),phi(k)/lambda(k)) divides k-1.
Problem: are there infinitely many such numbers?

Amiram Eldar, Table of n, a(n) for n = 1..10000
Index entries for sequences related to Carmichael numbers.

Cf. A000010, A002322, A002997, A034380, A173703.

Select[Range[3, 100000, 2], !PrimeQ[#] && Divisible[#-1, c = CarmichaelLambda[#]] && Divisible[c*(#-1), EulerPhi[#]] &]

A338998 Composite numbers k such that phi(k) divides p*(k - 1) for some prime factor p of k - 1.

Original entry on oeis.org

1729, 12801, 5079361, 34479361, 3069196417, 23915494401

Offset: 1

Tomohiro Yamada, Nov 18 2020

All terms of this sequence are terms of A337316 and all Lehmer numbers (if there are any) are contained in this sequence.
Terms 1729 and 3069196417 and several others are also Carmichael numbers (A002997), they are given in A339878.
The sequence also includes: 1334063001601, 6767608320001, 33812972024833, 380655711289345, 1584348087168001, 1602991137369601, 6166793784729601, 1531757211193440001. - Daniel Suteu, Nov 24 2020
Apparently, a(n) == 1 (mod 64). - Hugo Pfoertner, Dec 08 2020
The "Lehmer numbers" above refers to composite 1-Lehmer numbers, that is, numbers n that would satisfy the equation y * phi(n) = n-1, for some integer y > 1. Lehmer conjectured that no such numbers exist. See the assorted Web-links. - Antti Karttunen, Dec 26 2020

			phi(1729) = 1296 divides 3 * 1728.

D. H. Lehmer, On Euler's totient function, Bulletin of the American Mathematical Society, 38 (1932), 745-751.
Giovanni Resta, k-Lehmer numbers
Eric Weisstein's World of Mathematics, Lehmer's Totient Problem
Wikipedia, Lehmer's totient problem

Subsequence of A173703 (2-Lehmer numbers).
Cf. A337316 (with "squarefree divisor" instead of "prime factor").
Cf. A000010 (phi), A238574 (k-Lehmer numbers for some k), A339878 (Carmichael numbers in this sequence).

is(n)={my(s=denominator((n-1)/eulerphi(n))); !isprime(n) && isprime(s) && ((n-1)%s==0) && n>1}
{ forcomposite(n=1, 2^32, if(is(n), print1(n, ", "))) }

a(5) from Amiram Eldar, Nov 18 2020

a(6) from Daniel Suteu, confirmed by Max Alekseyev, Sep 29 2023

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

A207080 The smallest Carmichael number k such that phi(k) does not divide (k-1)^n, where phi is the Euler totient function.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A337316 Composite numbers k such that phi(k) divides d*(k - 1) for some squarefree divisor d of k - 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A277366 Composite numbers k such that phi(k)*lambda(k) divides (k-1)^2, where phi(k) = A000010(k) and lambda(k) = A002322(k).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Extensions

A306338 Carmichael numbers k such that phi(k) divides (k-1)*lambda(k).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A338998 Composite numbers k such that phi(k) divides p*(k - 1) for some prime factor p of k - 1.

Views

Author

Keywords