cp's OEIS Frontend

A355667 Least number phi(k) such that n * phi(k) < k, where phi is Euler's totient function.

%I A355667 #49 Mar 22 2025 23:34:07
%S A355667 1,2,8,48,5760,36495360,1854081073152000,
%T A355667 400440702414394285778534400000,
%U A355667 165062110921422523175104166476600499887194872217600000000
%N A355667 Least number phi(k) such that n * phi(k) < k, where phi is Euler's totient function.
%C A355667 a(n) is the Euler totient of A091456(n). Useful for calculating a simple upper bound of the inverse phi function.
%H A355667 Nico Mexis, <a href="/A355667/b355667.txt">Table of n, a(n) for n = 1..13</a>
%H A355667 John Abbott and Nico Mexis, <a href="https://arxiv.org/abs/2403.08751">Cyclotomic Factors and LRS-Degeneracy</a>, arXiv:2403.08751 [math.AC], 2024. See pp. 9, 24.
%F A355667 a(n) = A000010(A091456(n)).
%F A355667 a(n) = A000010(A091439(n+1)).
%e A355667 If we know n=276, then all numbers k with phi(k)=n will satisfy k < 5*n since m=a(5) is the first number in the sequence with n < m.
%t A355667 a[n_] := Module[{k = 1, p = 1, e}, While[k <= n*(e = EulerPhi[k]), p = NextPrime[p]; k *= p]; e]; Array[a, 9] (* _Amiram Eldar_, Jul 13 2022 *)
%o A355667 (PARI) a(n)=my(k=1); forprime(p=2, , if(n*eulerphi(k)<k, return(eulerphi(k)), k*=p))
%o A355667 (CoCoA) // CoCoA 5
%o A355667 define a(n) k := 1; p := 1; while k <= n*EulerTotient(k) do p := NextPrime(p); k := k*p; endwhile; return EulerTotient(k); enddefine;
%Y A355667 Totients of A091456 or A091439.
%K A355667 nonn
%O A355667 1,2
%A A355667 _Nico Mexis_, Jul 13 2022