A346094 a(n) = n / A275823(n), where A275823(n) is the least k such that n divides phi(k^2).

1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 4, 3, 2, 1, 2, 1, 2, 3, 2, 1, 2, 1, 4, 1, 2, 1, 2, 1, 2, 3, 4, 1, 6, 1, 2, 1, 2, 1, 4, 1, 2, 1, 4, 1, 6, 5, 2, 3, 2, 1, 4, 1, 2, 3, 4, 1, 2, 1, 4, 1, 2, 1, 2, 1, 2, 1, 2, 1, 6, 1, 4, 3, 2, 1, 6, 1, 2, 1, 2, 1, 2, 1, 2, 3, 2, 1, 4, 1, 2, 1, 4, 1, 2, 1, 4, 3

Offset: 1

Author

Antti Karttunen and Altug Alkan, Jul 21 2021

Keywords

• nonn

Comments

a(n) = n divided by the least k such that A002618(k) [= phi(k^2) = k*phi(k)] is a multiple of n.

It is easy to see that such k is always a divisor of n since k contains only some of prime factors of n and there cannot be other prime factor that does not divide n. In order to see this, let us assume p divides k (where p is prime that does not divide n) and (p-1) contribute the division in A275823. At this case there is definitely smaller option to do this instead of p-1 since it is always possible that k could contain necessary prime powers from factorization of p-1 instead of p. At the same time, obviously A275823(n) <= n. So terms of this sequence are always integers.

Crossrefs

Cf. A002618, A275823.

Programs

Mathematica

Array[#/Block[{k = 1}, While[! Mod[EulerPhi[k^2], #] == 0, k++]; k] &, 105] (* Michael De Vlieger, Jul 22 2021 *)

PARI

A346094(n) = { my(k=1); while((k*eulerphi(k)) % n, k++); (n/k); };