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,2

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.

Links

Jianing Song, Table of n, a(n) for n = 1..250

Formula

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

Example

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)

Prog

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

Crossrefs

Cf. A000010, A006530, A053287.

Sequence in context: A197862 A006530 A327398 * A102095 A331959 A109395

Adjacent sequences: A323613 A323614 A323615 * A323617 A323618 A323619

Keyword

nonn

Author

Jianing Song, Jan 20 2019

Status

approved