A323616 - OEIS

%I #26 Jan 29 2019 02:13:49

%S 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 11,331,2,293,257,439,3,1039,73,389,257,8501,43,2713,31,37,683,569,7,

%U 5419,5,257,31,131,19,29,241,10639,2179,8060489,11,1321,331,1289,17449

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

%C 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 It appears that each value occurs only a few times (see the Example section below), but to prove this seems nearly impossible.

%C 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 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 Jianing Song, <a href="/A323616/b323616.txt">Table of n, a(n) for n = 1..250</a>

%F a(n) = A006530(A053287(n)).

%e In the following list, a number k such that gpf(phi(2^k-1)) = gpf(k) is denoted with a "*".

%e a(n) = 1: 1* (1)

%e a(n) = 2: 2*, 4*, 8*, 16*, 32* (5)

%e a(n) = 3: 3*, 6*, 9*, 12*, 18*, 36* (6)

%e a(n) = 5: 5*, 10*, 15*, 20*, 24, 25*, 50* (7)

%e a(n) = 7: 7*, 14*, 21*, 28*, 48 (5)

%e a(n) = 11: 11*, 30, 60 (3)

%e a(n) = 13: 13*, 26* (2)

%e a(n) = 17: (0)

%e a(n) = 19: 27, 54, 108 (3)

%e a(n) = 23: (0)

%e a(n) = 29: 29*, 55 (2)

%e a(n) = 31: 22, 44, 52 (3)

%o (PARI) gpf(n) = if(n>1, vecmax(factor(n)[, 1]), 1);

%o a(n) = gpf(eulerphi(2^n-1))

%Y Cf. A000010, A006530, A053287.

%K nonn

%O 1,2

%A _Jianing Song_, Jan 20 2019