Good luck counting them all

Imagine $N$ points equally spaced on a circle. Imagine what is formed when each point is joined to another point, a fixed number $n$ of points clockwise round from the preceding point. If $n=1$ , each point is simply joined to its successor, forming the convex regular $N$ -gon. If $n=2$ , alternate points are joined, and so forth.

If $n$ and $N$ share a nontrivial common factor, then the resulting pattern is not a single polygon. For example, if $N=6$ and $n=2$ then the resulting shape is the "star of David" which consists of two superimposed triangles. Thus we obtain a single polygon provided that $n$ and $N$ are coprime.

Thus. if $N$ is odd, a total of $\phi(N)$ number of choices of $n$ exist which form a single regular polygon. This double-counts the number of possible polygons (joining every $n$ th vertex is similar to joining every $(N-n)$ th vertex). Thus there are $X_N = \tfrac12\phi(N)$ possible polygons.

If $N = 2^p-1$ is a Mersenne prime, then $X_N = \tfrac12(N-1) = 2^{p-1} - 1$ , and so the number of polygons is $2^n-1$ , where $n=p-1$ . Thus $\phi(n+1) = \phi(p) = p-1$ . This makes the answer to this question $\boxed{74207280}$ .