|
%I #55 Aug 10 2021 18:18:48
%S 561,1105,1729,2465,6601,8481,12801,15841,16705,19345,22321,30889,
%T 41041,46657,50881,52633,71905,75361,88561,93961,115921,126673,162401,
%U 172081,193249,247105,334153,340561,378561,449065,460801,574561,656601,658801,670033
%N Composite numbers n with the property that phi(n) divides (n-1)^2.
%C 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
%C McNew showed that the number of terms in this sequence below x is O(x^(6/7)). - _Tomohiro Yamada_, Sep 28 2020
%H Joerg Arndt and Donovan Johnson, <a href="/A173703/b173703.txt">Table of n, a(n) for n = 1..2000</a> (first 327 terms from Joerg Arndt)
%H José María Grau and Antonio M. Oller-Marcén, <a href="http://arxiv.org/abs/1012.2337">On k-Lehmer numbers</a>, Integers, 12(2012), #A37
%H Nathan McNew, <a href="https://doi.org/10.1142/S1793042113500218">Radically weakening the Lehmer and Carmichael conditions</a>, International Journal of Number Theory 9 (2013), 1215-1224; available from <a href="http://arxiv.org/abs/1210.2001">arXiv</a>, arXiv:1210.2001 [math.NT], 2012.
%H Romeo Meštrović, <a href="http://arxiv.org/abs/1305.1867">Generalizations of Carmichael numbers I,</a> arXiv:1305.1867v1 [math.NT], May 4, 2013.
%e a(1) = 561 is in the sequence because 560^2 = phi(561)*980 = 320*980 = 313600.
%p isA173703 := proc(n)
%p n <> 1 and not isprime(n) and (modp( (n-1)^2, numtheory[phi](n)) = 0 );
%p end proc:
%p for n from 1 to 10000 do
%p if isA173703(n) then
%p printf("%d,\n",n);
%p end if;
%p end do: # _R. J. Mathar_, Nov 06 2017
%t Union[Table[If[PrimeQ[n] === False && IntegerQ[(n-1)^2/EulerPhi[n]], n], {n, 3, 100000}]]
%t Select[Range[700000],CompositeQ[#]&&Divisible[(#-1)^2,EulerPhi[#]]&] (* _Harvey P. Dale_, Nov 29 2014 *)
%t Select[Range[1,700000,2],CompositeQ[#]&&PowerMod[#-1,2,EulerPhi[ #]] == 0&] (* _Harvey P. Dale_, Aug 10 2021 *)
%o (PARI)
%o N=10^9;
%o default(primelimit,N);
%o ct = 0;
%o { for (n=4, N,
%o if ( ! isprime(n),
%o if ( ( (n-1)^2 % eulerphi(n) ) == 0,
%o ct += 1;
%o print(ct," ",n);
%o );
%o );
%o ); }
%o /* _Joerg Arndt_, Jun 23 2012 */
%Y Cf. A000010, A207080.
%Y Cf. A238574 (k-Lehmer numbers for some k).
%K nonn
%O 1,1
%A _José María Grau Ribas_, Nov 25 2010
|
