cp's OEIS Frontend

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

%I A173703 #55 Aug 10 2021 18:18:48
%S A173703 561,1105,1729,2465,6601,8481,12801,15841,16705,19345,22321,30889,
%T A173703 41041,46657,50881,52633,71905,75361,88561,93961,115921,126673,162401,
%U A173703 172081,193249,247105,334153,340561,378561,449065,460801,574561,656601,658801,670033
%N A173703 Composite numbers n with the property that phi(n) divides (n-1)^2.
%C A173703 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 A173703 McNew showed that the number of terms in this sequence below x is O(x^(6/7)). - _Tomohiro Yamada_, Sep 28 2020
%H A173703 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 A173703 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 A173703 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 A173703 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 A173703 a(1) = 561 is in the sequence because 560^2 = phi(561)*980 = 320*980 = 313600.
%p A173703 isA173703 := proc(n)
%p A173703     n <> 1 and not isprime(n) and (modp( (n-1)^2, numtheory[phi](n)) = 0 );
%p A173703 end proc:
%p A173703 for n from 1 to 10000 do
%p A173703     if isA173703(n) then
%p A173703         printf("%d,\n",n);
%p A173703     end if;
%p A173703 end do: # _R. J. Mathar_, Nov 06 2017
%t A173703 Union[Table[If[PrimeQ[n] === False && IntegerQ[(n-1)^2/EulerPhi[n]], n], {n, 3, 100000}]]
%t A173703 Select[Range[700000],CompositeQ[#]&&Divisible[(#-1)^2,EulerPhi[#]]&] (* _Harvey P. Dale_, Nov 29 2014 *)
%t A173703 Select[Range[1,700000,2],CompositeQ[#]&&PowerMod[#-1,2,EulerPhi[ #]] == 0&] (* _Harvey P. Dale_, Aug 10 2021 *)
%o A173703 (PARI)
%o A173703 N=10^9;
%o A173703 default(primelimit,N);
%o A173703 ct = 0;
%o A173703 { for (n=4, N,
%o A173703     if ( ! isprime(n),
%o A173703         if ( ( (n-1)^2 % eulerphi(n) ) == 0,
%o A173703             ct += 1;
%o A173703             print(ct," ",n);
%o A173703         );
%o A173703     );
%o A173703 ); }
%o A173703 /* _Joerg Arndt_, Jun 23 2012 */
%Y A173703 Cf. A000010, A207080.
%Y A173703 Cf. A238574 (k-Lehmer numbers for some k).
%K A173703 nonn
%O A173703 1,1
%A A173703 _José María Grau Ribas_, Nov 25 2010