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

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

A254352 a(n) is the least composite x such that sigma(x) divides (x-1)^n but not (x-1)^(n-1), for n >= 2.

Original entry on oeis.org

385, 21, 93, 235, 2899, 903, 1771, 3619, 651, 11935, 2667, 48895, 11811, 27559, 415555, 848995, 172011, 3153535, 761763, 1777447, 2752491, 7281799, 11010027, 28442407, 48758691, 113770279, 199753347, 466091143, 677207307, 2064117919, 3220807683, 7515217927

Offset: 2

Paolo P. Lava, Jan 30 2015

nonn

			sigma(385) = 576; (385 - 1)^2 = 21743271936 and 21743271936 / 576 = 37748736.
sigma(21) = 32; (21 - 1)^3 = 8000 and 8000 / 32 = 250.
sigma(93) = 128; (93 - 1)^4 = 71639296 and 71639296 / 128 = 559682.

Cf. A000203, A234936, A254409.

with(numtheory):P:=proc(q) local a,j,k,n; for k from 2 to q do
for n from 1 to q do if not isprime(n) then
if type((n-1)^k/sigma(n),integer) then
if not type((n-1)^(k-1)/sigma(n),integer) then lprint(k,n);
break; fi; fi; fi; od; od;end: P(10^9);

a[n_] := Module[{k=4, s=7}, While[PrimeQ[k] || !(PowerMod[k-1, n, s] == 0 && PowerMod[k-1, n-1, s] > 0), k++; s=DivisorSigma[1, k]]; k]; Array[a, 11, 2] (* Amiram Eldar, Apr 08 2019 *)

a(n) = {x = 4; sx = sigma(x); while(! (((x-1)^(n-1) % sx) && !((x-1)^n % sx)), x++; while (isprime(x), x++); sx = sigma(x)); x;} \\ Michel Marcus, Jan 30 2015

isok(x, n) = my(sx=sigma(x)); (((x-1)^(n-1) % sx) && !((x-1)^n % sx));
a(n) = forcomposite(x=4, , if (isok(x, n), return(x))); \\ Michel Marcus, Apr 08 2019

a(22)-a(33) from Amiram Eldar, Apr 08 2019

A254409 a(n) is the least x such that tau(x) divides (x-1)^n but not (x-1)^(n-1), for n >= 2.

Original entry on oeis.org

15, 135, 1155, 10395, 135135, 2297295, 57432375, 1003917915, 25097947875

Offset: 2

Paolo P. Lava, Jan 30 2015

So far, all terms appear to be multiples of 15.
It appears that tau(a(n)) is equal to 2^n. For instance, for n=3, a(3)=135 and 135 has 2^3=8 divisors.
The quotients tau(a(n))/(a(n)-1)^n are: 7^2, 67^3, 577^4, 5197^5, 67567^6, 1148647^7, 28716187^8, 501958957^9, ... - Michel Marcus, Feb 13 2015
Assuming that tau(a(n)) is 2^n (which would appear to follow from the minimality of a(n) and the fact that tau(a(n)) must be divisible by an n-th power), a(n)-1 would have to contain a solitary factor of 2, and so a(n) would be the least number congruent to 3 modulo 4 such that tau(a(n)) = 2^n. The next few terms would appear to be a(9)*25, a(9)*25*29, a(9)*25*29*37, a(9)*25*29*31*43, and a(9)*25*29*31*37*43. - Charlie Neder, Aug 19 2018

			tau(15) = 4; (15 - 1)^2 = 196 and 196 / 4 = 49.
tau(135) = 8; (135 - 1)^3 = 2406104 and 2406104 / 8 = 300763.
tau(1155) = 16; (1155 - 1)^4 = 1773467504656 and 1773467504656 / 16 = 110841719041.

Cf. A000005 (tau(n)), A234936, A254352.

with(numtheory):P:=proc(q) local a,j,k,n; for k from 2 to q do
for n from 1 to q do if not isprime(n) then
if type((n-1)^k/tau(n),integer) then
if not type((n-1)^(k-1)/tau(n),integer) then print(n);
break; fi; fi; fi; od; od;end: P(10^9);

for(n=2, 10, forcomposite(x=1, , if(Mod((x-1)^n, numdiv(x))==0 && Mod((x-1)^(n-1), numdiv(x))!=0, print1(x, ", "); break({1})))) \\ Felix Fröhlich, Feb 12 2015

isok(k, n) = {my(m = Mod(k-1, numdiv(k))); (m^(n-1) != 0) && (m^n == 0);}
a(n) = {my(k=2); while(!isok(k, n), k++); k}; \\ Michel Marcus, Aug 20 2018

a(8)-a(9) from Felix Fröhlich, Feb 12 2015

a(10) from Amiram Eldar, Jul 02 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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A254352 a(n) is the least composite x such that sigma(x) divides (x-1)^n but not (x-1)^(n-1), for n >= 2.

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Extensions

A254409 a(n) is the least x such that tau(x) divides (x-1)^n but not (x-1)^(n-1), for n >= 2.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

PARI

PARI

Extensions