A280990 - OEIS

%I #31 Sep 26 2020 16:29:56

%S 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 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 11,7,19,29,59,31,61,31,7,2,131,67,67,17,139,71,71,3,73,37,31,19,463

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

%C n*a(n) are 2, 4, 9, 8, 25, 18, 49, 16, 27, 50, 121, 36, 169, 98, 465, 32, 289, ...

%C a(n) <= A034694(A007947(n)). If n is in A050384 then a(n) = A034694(n). - _Robert Israel_, Jan 12 2017

%H Robert Israel, <a href="/A280990/b280990.txt">Table of n, a(n) for n = 1..10000</a>

%F a(p^k) = p for all primes p and k >= 1. - _Robert Israel_, Jan 12 2017

%F a(n) << n^5 by Xylouris' improvement to Linnik's theorem. - _Charles R Greathouse IV_, Jan 20 2017

%e 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 f:= proc(n) local p;

%p     p:= 2;

%p     while numtheory:-phi(p*n) mod n <> 0 do p:= nextprime(p) od:

%p     p

%p end proc:

%p map(f, [$1..100]); # _Robert Israel_, Jan 12 2017

%t 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 (PARI) a(n)=my(k = 1); while (eulerphi(prime(k)*n) % n != 0, k++); prime(k);

%o (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 Cf. A000010, A007694, A007947, A034694, A050384, A109395.

%Y Cf. A000079, A065119, A086761: for those n such that a(n)=2,3,5. - _Michel Marcus_, Jan 20 2017

%K nonn

%O 1,1

%A _Altug Alkan_, Jan 12 2017