A207080 -id:A207080 - 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 */

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

Original entry on oeis.org

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

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