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

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, 11, 331, 2, 293, 257, 439, 3, 1039, 73, 389, 257, 8501, 43, 2713, 31, 37, 683, 569, 7, 5419, 5, 257, 31, 131, 19, 29, 241, 10639, 2179, 8060489, 11, 1321, 331, 1289, 17449

Offset: 1

Author

Jianing Song, Jan 20 2019

Keywords

• nonn

Comments

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.

It appears that each value occurs only a few times (see the Example section below), but to prove this seems nearly impossible.

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.

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.

Examples

			In the following list, a number k such that gpf(phi(2^k-1)) = gpf(k) is denoted with a "*".
a(n) = 1: 1* (1)
a(n) = 2: 2*, 4*, 8*, 16*, 32* (5)
a(n) = 3: 3*, 6*, 9*, 12*, 18*, 36* (6)
a(n) = 5: 5*, 10*, 15*, 20*, 24, 25*, 50* (7)
a(n) = 7: 7*, 14*, 21*, 28*, 48 (5)
a(n) = 11: 11*, 30, 60 (3)
a(n) = 13: 13*, 26* (2)
a(n) = 17: (0)
a(n) = 19: 27, 54, 108 (3)
a(n) = 23: (0)
a(n) = 29: 29*, 55 (2)
a(n) = 31: 22, 44, 52 (3)
		

Links

• Amiram Eldar, Table of n, a(n) for n = 1..512 (terms 1..250 from Jianing Song)

Crossrefs

Cf. A000010, A006530, A053287.

Programs

Mathematica

a[n_] := FactorInteger[EulerPhi[2^n-1]][[-1, 1]]; Array[a, 64] (* Amiram Eldar, Mar 02 2025 *)

PARI

gpf(n) = if(n>1, vecmax(factor(n)[, 1]), 1);
a(n) = gpf(eulerphi(2^n-1))

Formula

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