A165774 - OEIS

%I #23 Nov 11 2024 05:28:08

%S 2,6,18,90,462,3150,22050,210210,1891890,19969950,219669450,

%T 2847714870,37020293310,520843112790,7959363061650,135309172048050,

%U 2300255924816850,41996101027370490,797925919520039310,16504589035937252250,347097774991217099850,7751850308137181896650,179602728970220622816750,4493489228616853106091450,112337230715421327652286250,2958213742172761628176871250,79871771038664563960775523750,2279417465795734863803670716250

%N Largest solution to phi(x) = n!, where phi() is Euler totient function (A000010).

%C All solutions to phi(x) = n! belong to the interval [n!,(n+1)!] and are listed in the n-th row of A165773 (when written as table with row lengths A055506). Thus this sequence gives the last element in these rows, i.e., a(n) = A165773(Sum_{k=1..n} A055506(k)).

%C All terms in this sequence are even, since if x is an odd solution to phi(x) = n!, then 2x is a larger solution because phi(2x) = phi(2)*phi(x) = phi(x).

%C Most terms (and any term divisible by 4) are divisible by 3, since if x = 2^k*y is a solution with k>1 and gcd(y,2*3) = 1, then x*3/2 = 2^(k-1)*3*y is a larger solution because phi(2^(k-1)*3) = 2^(k-2)*(3-1) = 2^(k-1) = phi(2^k).

%C For the same reason, most terms are divisible by 5, since if x=2^k*y is a solution with k>2 and gcd(y,2*5) = 1, then x*5/4 is a larger solution.

%C Also, any term of the form x = 2^k*3^m*y with k,m>1 must be divisible by 7 (else x*7/6 would be a larger solution), and so on.

%C Experimentally, a(n) = c(n)*(n+1)! with a coefficient c(n) ~ 2^(-n/10) (e.g., c(1) = c(2) = 1, c(10) ~ 0.5).

%H Max A. Alekseyev, <a href="https://www.emis.de/journals/JIS/VOL19/Alekseyev/alek5.html">Computing the Inverses, their Power Sums, and Extrema for Euler's Totient and Other Multiplicative Functions</a>. Journal of Integer Sequences, Vol. 19 (2016), Article 16.5.2.

%H Max Alekseyev, <a href="https://oeis.org/wiki/User:Max_Alekseyev/gpscripts">PARI/GP Scripts for Miscellaneous Math Problems</a> (invphi.gp).

%e a(1) = 2 is the largest among the A055506(1) = 2 solutions {1,2} to phi(n) = 1! = 1.

%e a(4) = 90 is the largest among the A055506(4) = 10 solutions {35, 39, 45, 52, 56, 70, 72, 78, 84, 90} to phi(n) = 4! = 24.

%e See A165773 for more examples.

%o (PARI) a(n) = invphiMax(n!); \\ _Amiram Eldar_, Nov 11 2024, using _Max Alekseyev_'s invphi.gp

%Y Cf. A000010, A055487, A055506, A055489, A014197, A165773.

%K nonn

%O 1,1

%A _M. F. Hasler_, Oct 04 2009

%E Edited and terms a(12)-a(28) added by _Max Alekseyev_, Jan 26 2012, Jul 09 2014