cp's OEIS Frontend

A323616 a(n) is the largest prime factor of phi(2^n-1), where phi is Euler's totient.

%I A323616 #33 Mar 02 2025 07:59:48
%S A323616 1,2,3,2,5,3,7,2,3,5,11,3,13,7,5,2,257,3,73,5,7,31,97,5,5,13,19,7,29,
%T A323616 11,331,2,293,257,439,3,1039,73,389,257,8501,43,2713,31,37,683,569,7,
%U A323616 5419,5,257,31,131,19,29,241,10639,2179,8060489,11,1321,331,1289,17449
%N A323616 a(n) is the largest prime factor of phi(2^n-1), where phi is Euler's totient.
%C A323616 If a(n) <= 2, then a regular (2^n-1)-gon can be constructed using a straightedge and compass; if a(n) <= 3, then a regular (2^n-1)-gon can be constructed using a straightedge, compass and an angle-trisector, etc.
%C A323616 It appears that each value occurs only a few times (see the Example section below), but to prove this seems nearly impossible.
%C A323616 Although a(n) = gpf(n) for the first few n, it should more often be the case that a(n) is relatively large compared to n. It seems that gpf(phi(2^n-1)) = gpf(n) only for n = 1..16, 18, 20, 21, 25, 26, 28, 29, 32, 36, 50. See the Example section below.
%C A323616 Nevertheless, there are many n such that a(n) = a(2*n) (including 44 of the first 100 terms). Moreover, if phi(2^n-1) and phi(2^n+1) have exactly the same prime factors, then phi(2^(2*n)-1) = phi(2^n-1)*phi(2^n+1) is powerful, and this holds for 2*n = 4, 6, 8, 12, 14, 16, 18, 26, 32, 36, 38, 50, 60, 62, 76, 108, 122, 254. By the way, phi(2^n-1) is also powerful for n = 9, 11, 15, 21, 25, 28, and there seem to be no other such numbers n.
%H A323616 Amiram Eldar, <a href="/A323616/b323616.txt">Table of n, a(n) for n = 1..512</a> (terms 1..250 from Jianing Song)
%F A323616 a(n) = A006530(A053287(n)).
%e A323616 In the following list, a number k such that gpf(phi(2^k-1)) = gpf(k) is denoted with a "*".
%e A323616 a(n) = 1: 1* (1)
%e A323616 a(n) = 2: 2*, 4*, 8*, 16*, 32* (5)
%e A323616 a(n) = 3: 3*, 6*, 9*, 12*, 18*, 36* (6)
%e A323616 a(n) = 5: 5*, 10*, 15*, 20*, 24, 25*, 50* (7)
%e A323616 a(n) = 7: 7*, 14*, 21*, 28*, 48 (5)
%e A323616 a(n) = 11: 11*, 30, 60 (3)
%e A323616 a(n) = 13: 13*, 26* (2)
%e A323616 a(n) = 17: (0)
%e A323616 a(n) = 19: 27, 54, 108 (3)
%e A323616 a(n) = 23: (0)
%e A323616 a(n) = 29: 29*, 55 (2)
%e A323616 a(n) = 31: 22, 44, 52 (3)
%t A323616 a[n_] := FactorInteger[EulerPhi[2^n-1]][[-1, 1]]; Array[a, 64] (* _Amiram Eldar_, Mar 02 2025 *)
%o A323616 (PARI) gpf(n) = if(n>1, vecmax(factor(n)[, 1]), 1);
%o A323616 a(n) = gpf(eulerphi(2^n-1))
%Y A323616 Cf. A000010, A006530, A053287.
%K A323616 nonn
%O A323616 1,2
%A A323616 _Jianing Song_, Jan 20 2019