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

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

Offset

1,1

Comments

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

a(n) <= A034694(A007947(n)). If n is in A050384 then a(n) = A034694(n). - Robert Israel, Jan 12 2017

Links

Robert Israel, Table of n, a(n) for n = 1..10000

Formula

a(p^k) = p for all primes p and k >= 1. - Robert Israel, Jan 12 2017

a(n) << n^5 by Xylouris' improvement to Linnik's theorem. - Charles R Greathouse IV, Jan 20 2017

Example

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.

Maple

f:= proc(n) local p;
    p:= 2;
    while numtheory:-phi(p*n) mod n <> 0 do p:= nextprime(p) od:
    p
end proc:
map(f, [$1..100]); # Robert Israel, Jan 12 2017

Mathematica

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 *)

Prog

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

Crossrefs

Cf. A000010, A007694, A007947, A034694, A050384, A109395.

Cf. A000079, A065119, A086761: for those n such that a(n)=2,3,5. - Michel Marcus, Jan 20 2017

Sequence in context: A111089 A051664 A318884 * A327667 A256267 A307687

Adjacent sequences: A280987 A280988 A280989 * A280991 A280992 A280993

Keyword

nonn

Author

Altug Alkan, Jan 12 2017

Status

approved