A238574 -id:A238574 - cp's OEIS frontend

A173703 Composite numbers n with the property that phi(n) divides (n-1)^2.

561, 1105, 1729, 2465, 6601, 8481, 12801, 15841, 16705, 19345, 22321, 30889, 41041, 46657, 50881, 52633, 71905, 75361, 88561, 93961, 115921, 126673, 162401, 172081, 193249, 247105, 334153, 340561, 378561, 449065, 460801, 574561, 656601, 658801, 670033

Offset: 1

José María Grau Ribas, Nov 25 2010

nonn

All terms are odd because if n is even, (n-1)^2 is odd and phi(n) is even for n > 2. - Donovan Johnson, Sep 08 2013

McNew showed that the number of terms in this sequence below x is O(x^(6/7)). - Tomohiro Yamada, Sep 28 2020

			a(1) = 561 is in the sequence because 560^2 = phi(561)*980 = 320*980 = 313600.

Joerg Arndt and Donovan Johnson, Table of n, a(n) for n = 1..2000 (first 327 terms from Joerg Arndt)
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, International Journal of Number Theory 9 (2013), 1215-1224; available from arXiv, arXiv:1210.2001 [math.NT], 2012.
Romeo Meštrović, Generalizations of Carmichael numbers I, arXiv:1305.1867v1 [math.NT], May 4, 2013.

Cf. A000010, A207080.

Cf. A238574 (k-Lehmer numbers for some k).

isA173703 := proc(n)
    n <> 1 and not isprime(n) and (modp( (n-1)^2, numtheory[phi](n)) = 0 );
end proc:
for n from 1 to 10000 do
    if isA173703(n) then
        printf("%d,\n",n);
    end if;
end do: # R. J. Mathar, Nov 06 2017

Union[Table[If[PrimeQ[n] === False && IntegerQ[(n-1)^2/EulerPhi[n]], n], {n, 3, 100000}]]
Select[Range[700000],CompositeQ[#]&&Divisible[(#-1)^2,EulerPhi[#]]&] (* Harvey P. Dale, Nov 29 2014 *)
Select[Range[1,700000,2],CompositeQ[#]&&PowerMod[#-1,2,EulerPhi[ #]] == 0&] (* Harvey P. Dale, Aug 10 2021 *)

N=10^9;
default(primelimit,N);
ct = 0;
{ for (n=4, N,
    if ( ! isprime(n),
        if ( ( (n-1)^2 % eulerphi(n) ) == 0,
            ct += 1;
            print(ct," ",n);
        );
    );
); }
/* Joerg Arndt, Jun 23 2012 */

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

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

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[#]] &]

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

A173703 Composite numbers n with the property that phi(n) divides (n-1)^2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A238575 k-Lehmer numbers with two prime factors.

Views

Author

Keywords

Comments

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

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Extensions