cp's OEIS Frontend

A280990 Least prime p such that n divides phi(p*n).

%I A280990 #31 Sep 26 2020 16:29:56
%S A280990 2,2,3,2,5,3,7,2,3,5,11,3,13,7,31,2,17,3,19,5,7,11,23,3,5,13,3,7,29,
%T A280990 31,31,2,67,17,71,3,37,19,13,5,41,7,43,11,31,23,47,3,7,5,103,13,53,3,
%U A280990 11,7,19,29,59,31,61,31,7,2,131,67,67,17,139,71,71,3,73,37,31,19,463
%N A280990 Least prime p such that n divides phi(p*n).
%C A280990 n*a(n) are 2, 4, 9, 8, 25, 18, 49, 16, 27, 50, 121, 36, 169, 98, 465, 32, 289, ...
%C A280990 a(n) <= A034694(A007947(n)). If n is in A050384 then a(n) = A034694(n). - _Robert Israel_, Jan 12 2017
%H A280990 Robert Israel, <a href="/A280990/b280990.txt">Table of n, a(n) for n = 1..10000</a>
%F A280990 a(p^k) = p for all primes p and k >= 1. - _Robert Israel_, Jan 12 2017
%F A280990 a(n) << n^5 by Xylouris' improvement to Linnik's theorem. - _Charles R Greathouse IV_, Jan 20 2017
%e A280990 a(15) = 31 because 15 does not divide phi(p*15) for p < 31 where p is prime and phi(31*15) = 2*4*30 is divisible by 15.
%p A280990 f:= proc(n) local p;
%p A280990     p:= 2;
%p A280990     while numtheory:-phi(p*n) mod n <> 0 do p:= nextprime(p) od:
%p A280990     p
%p A280990 end proc:
%p A280990 map(f, [$1..100]); # _Robert Israel_, Jan 12 2017
%t A280990 lpp[n_]:=Module[{p=2},While[Mod[EulerPhi[p*n],n]!=0,p=NextPrime[p]];p]; Array[lpp,80] (* _Harvey P. Dale_, Sep 26 2020 *)
%o A280990 (PARI) a(n)=my(k = 1); while (eulerphi(prime(k)*n) % n != 0, k++); prime(k);
%o A280990 (PARI) a(n)=my(t=n/gcd(eulerphi(n),n)); if(t==1, return(2)); forstep(p=if(t%2,2*t,t)+1, if(isprime(t), t, oo),lcm(t,2), if(isprime(p), return(p))); t \\ _Charles R Greathouse IV_, Jan 20 2017
%Y A280990 Cf. A000010, A007694, A007947, A034694, A050384, A109395.
%Y A280990 Cf. A000079, A065119, A086761: for those n such that a(n)=2,3,5. - _Michel Marcus_, Jan 20 2017
%K A280990 nonn
%O A280990 1,1
%A A280990 _Altug Alkan_, Jan 12 2017