A275823 Least k such that n divides phi(k^2).

1, 2, 3, 4, 5, 3, 7, 4, 9, 5, 11, 6, 13, 7, 15, 8, 17, 9, 19, 5, 7, 11, 23, 12, 25, 13, 9, 14, 29, 15, 31, 8, 33, 17, 35, 18, 37, 19, 13, 10, 41, 7, 43, 22, 45, 23, 47, 12, 49, 25, 51, 13, 53, 9, 11, 28, 19, 29, 59, 15, 61, 31, 21, 16, 65, 33, 67, 17, 69, 35, 71, 36, 73, 37, 75, 38, 77, 13, 79, 20

Offset: 1

Author

Altug Alkan, Aug 10 2016

Keywords

• nonn
• easy

Examples

			a(54) = 9 because 54 divides phi(9^2) = 54.
		

Links

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

Crossrefs

Cf. A002618.

Programs

Maple

N:= 100: # to get a(1)..a(N)
S:= {$1..N}: A:= 'A':
for k from 1 while S <> {} do
   r:= numtheory:-phi(k^2);
   E:= select(t -> r mod t = 0, S);
   if E <> {} then
     assign(seq(A[e],e=E) = seq(k ,e=E));
     S:= S minus E;
   fi
od:
seq(A[i],i=1..N); # Robert Israel, Aug 10 2016

Mathematica

Table[k = 1; While[! Divisible[EulerPhi[k^2], n], k++]; k, {n, 80}] (* Michael De Vlieger, Aug 10 2016 *)

PARI

a(n) = {my(k=1); while(eulerphi(k^2) % n, k++); k; }

Formula

a(n) <= n.

From Robert Israel, Aug 10 2016: (Start)

a(n) >= sqrt(n).

If n is prime or the square of a prime, then a(n) = n.

If n = m^j, then a(n) <= m^ceiling((j+1)/2). (End)