正 65537 边形的尺规作图

cancan123456

SD 现役 OIer，初三，Googology 爱好者

Carlyle Circle

考虑两个数 s,p ，其可以确定一个二次方程 x^2-sx+p=0 ，在给定 s,p 的情况下，我们可以尺规作图求出其两个根。

那么有没有很简单的方法？有。

我们作两个点 (0,1) 和 (s,p) ，以其为直径作圆，该圆交于 x 轴于两点，则这两点为 x^2-sx+p 的两个根。

这个方法就叫 Carlyle Circle。

我们先从正十七边形入手，因为其计算量小。

单位根

我们令 \omega_n^k=\cos\left(\dfrac{2\pi k}n\right)+i\sin\left(\dfrac{2\pi k}n\right)=\exp\left(\dfrac{2\pi k}n\right) ，那么我们只需要求出 \omega_{17}^0,\omega_{17}^1,\omega_{17}^2,\dots,\omega_{17}^{16} 然后在复平面上依次连接即可得到正十七边形。

而 \omega_{17}^0 是平凡的，其显然为 1 ，所以我们不用考虑它。

下面需要用到的性质：

\omega_n^{k_1}\omega_n^{k_2}=\exp\left(\dfrac{2\pi k_1}n\right)\exp\left(\dfrac{2\pi k_2}n\right)=\exp\left(\dfrac{2\pi k_1}n+\dfrac{2\pi k_1}n\right)=\exp\left(\dfrac{2\pi(k_1+k_2)}n\right)=\omega_n^{k_1+k_2}

\omega_n^k=\cos\left(\dfrac{2\pi k}n\right)+i\cos\left(\dfrac{2\pi k}n\right)=\cos\left(\dfrac{2\pi k}n+2\pi\right)+i\cos\left(\dfrac{2\pi k}n+2\pi\right)=\cos\left(\dfrac{2\pi(k+n)}n\right)+i\cos\left(\dfrac{2\pi(k+n)}n+2\pi\right)=\omega_n^{k+n}

分组

我们都知道 17=2^{2^2}+1 ，是一个费马素数，众所周知所有费马素数都有原根 3 ，所以我们尝试按照 3 的幂分组。

具体地，我们设

\begin{cases}\alpha_0=\sum_{i=0}^{7}\omega_{17}^{3^{2i}}=\omega_{17}^1+\omega_{17}^9+\omega_{17}^{13}+\omega_{17}^{15}+\omega_{17}^{16}+\omega_{17}^8+\omega_{17}^4+\omega_{17}^2\\\alpha_1=\sum_{i=0}^{7}\omega_{17}^{3^{2i+1}}=\omega_{17}^3+\omega_{17}^{10}+\omega_{17}^5+\omega_{17}^{11}+\omega_{17}^{14}+\omega_{17}^7+\omega_{17}^{12}+\omega_{17}^6\end{cases}

则有 \begin{cases}\alpha_0+\alpha_1&=-1\\\alpha_0\alpha_1&=-4\end{cases} ，由这两个式子和数值计算我们可以得到：

\alpha_{0,1}=\dfrac{-1\pm\sqrt{17}}2

再设

\beta_i=\sum_{j=0}^3\omega_{17}^{3^{4j+i}}(0\le i<4)

则有

\begin{cases}\beta_0=\omega_{17}^1+\omega_{17}^{13}+\omega_{17}^{16}+\omega_{17}^4\\\beta_1=\omega_{17}^3+\omega_{17}^5+\omega_{17}^{14}+\omega_{17}^{12}\\\beta_2=\omega_{17}^9+\omega_{17}^{15}+\omega_{17}^8+\omega_{17}^2\\\beta_3=\omega_{17}^{10}+\omega_{17}^{11}+\omega_{17}^7+\omega_{17}^6\end{cases}

通过简单的计算我们有：

\begin{cases}\beta_0+\beta_2&=\alpha_0\\\beta_0\beta_2&=-1\end{cases}

\begin{cases}\beta_1+\beta_3&=\alpha_1\\\beta_1\beta_3&=-1\end{cases}

再结合数值计算可以解出来：

\begin{cases}\beta_{0,2}&=\dfrac{\alpha_0\pm\sqrt{\alpha_0^2+4}}2\\\beta_{1,3}&=\dfrac{\alpha_1\pm\sqrt{\alpha_1^2+4}}2\end{cases}

我们再设：

\gamma_i=\sum_{j=0}^1\omega_{17}^{3^{8j+i}}(0\le i<8)

注意我们只需要求出 \gamma_0 的值即可，我们可以得到：

\begin{cases}\gamma_0+\gamma_1&=\omega_{17}^1+\omega_{17}^{16}+\omega_{17}^{13}+\omega_{17}^4=\beta_0\\\gamma_0\gamma_1&=\omega_{17}^{14}+\omega_{17}^5+\omega_{17}^{12}+\omega_{17}^3=\beta_1\end{cases}

解得：

\gamma_{0,1}=\dfrac{\beta_0\pm\sqrt{\beta_0^2-4\beta_1}}2

注意到 \gamma_0=\omega_{17}^0+\omega_{17}^{16} ，不难证明 \omega_{17}^0 和 \omega_{17}^{16} 实部相同，虚部为相反数，所以 \gamma_0=2\Re(\omega_{17}^1) ，再根据 |\omega_{17}^1|=1 就可以求出 \omega_{17}^1 了。

总结一下，就是：

z=\dfrac{\dfrac{\dfrac{-1+\sqrt{17}}2+\sqrt{\left(\dfrac{-1+\sqrt{17}}2\right)^2+4}}2+\sqrt{\left(\dfrac{\dfrac{-1+\sqrt{17}}2+\sqrt{\left(\dfrac{-1+\sqrt{17}}2\right)^2+4}}2\right)^2-4\left(\dfrac{\dfrac{-1-\sqrt{17}}2+\sqrt{\left(\dfrac{-1-\sqrt{17}}2\right)^2+4}}2\right)}}4

\omega_{17}^1=z+i\sqrt{1-z^2}

然后就可以画出正 17 边形了。

上面这些东西都是可以手算的。

正 257 边形

同理，我们设：

\begin{cases}a_j=\sum_{i=0}^{127}\omega_{257}^{3^{2i+j}}&(0\le j<2)\\b_j=\sum_{i=0}^{63}\omega_{257}^{3^{4i+j}}&(0\le j<4)\\c_j=\sum_{i=0}^{31}\omega_{257}^{3^{8i+j}}&(0\le j<8)\\d_j=\sum_{i=0}^{15}\omega_{257}^{3^{16i+j}}&(0\le j<16)\\e_j=\sum_{i=0}^7\omega_{257}^{3^{32i+j}}&(0\le j<32)\\f_j=\sum_{i=0}^3\omega_{257}^{3^{64i+j}}&(0\le j<64)\\g_j=\sum_{i=0}^1\omega_{257}^{3^{128i+j}}&(0\le j<128)\end{cases}

然后爆算即可。

可能中间的结果有一点长，可以写个程序算一算，可以得到：

\begin{cases}g_0+g_{64}=f_0\\g_0g_{64}=f_{56}\\g_0>g_{64}\\f_0+f_{32}=e_0\\f_0f_{32}=e_1+e_{23}\\f_0>f_{32}\\f_{24}+f_{56}=e_{24}\\f_{24}f_{56}=e_{15}+e_{25}\\f_{24}<f_{56}\\e_0+e_{16}=d_0\\e_0e_{16}=d_0+d_1+d_2+d_5\\e_0>e_{16}\\e_1+e_{17}=d_1\\e_1e_{17}=d_1+d_2+d_3+d_6\\e_1>e_{17}\\e_7+e_{23}=d_7\\e_7e_{23}=d_7+d_8+d_9+d_{12}\\e_7<e_{23}\\e_8+e_{24}=d_8\\e_8e_{24}=d_8+d_9+d_{10}+d_{13}\\e_8<e_{24}\\e_9+e_{25}=d_9\\e_9e_{25}=d_9+d_{10}+d_{11}+d_{14}\\e_9<e_{25}\\e_{15}+e_{31}=d_{15}\\e_{15}e_{31}=d_0+d_1+d_4+d_{15}\\e_{15}>e_{31}\\d_0+d_8=c_0\\d_0d_8=2c_0+2c_2+c_4+2c_5+c_6\\d_0>d_8\\d_1+d_9=c_1\\d_1d_9=2c_1+2c_3+c_5+2c_6+c_7\\d_1>d_9\\d_2+d_{10}=c_2\\d_2d_{10}=c_0+2c_2+2c_4+c_6+2c_7\\d_2>d_{10}\\d_3+d_{11}=c_3\\d_3d_{11}=2c_0+c_1+2c_3+2c_5+c_7\\d_3>d_{11}\\d_4+d_{12}=c_4\\d_4d_{12}=c_0+2c_1+c_2+2c_4+2c_6\\d_4>d_{12}\\d_5+d_{13}=c_5\\d_5d_{13}=c_1+2c_2+c_3+2c_5+2c_7\\d_5>d_{13}\\d_6+d_{14}=c_6\\d_6d_{14}=2c_0+c_2+2c_3+c_4+2c_6\\d_6<d_{14}\\d_7+d_{15}=c_7\\d_7d_{15}=2c_1+c_3+2c_4+c_5+2c_7\\d_7>d_{15}\\c_0+c_4=b_0\\c_0c_4=2b_0+5b_1+4b_2+5b_3\\c_0>c_4\\c_1+c_5=b_1\\c_1c_5=5b_0+2b_1+5b_2+4b_3\\c_1<c_5\\c_2+c_6=b_2\\c_2c_6=4b_0+5b_1+2b_2+5b_3\\c_2>c_6\\c_3+c_7=b_3\\c_3c_7=5b_0+4b_1+5b_2+2b_3\\c_3<c_7\\b_0+b_2=a_0\\b_0b_2=16a_0+16a_1\\b_0>b_2\\b_1+b_3=a_1\\b_1b_3=16a_0+16a_1\\b_1>b_3\\a_0+a_1=z_0\\a_0a_1=64z_0\\a_0>a_1\\z_0=-1\end{cases}

实际操作在这里：正 257 边形。

正 65537 边形与此类似，扔一下代码：

#include <iostream>
#include <complex>
#include <vector>
using namespace std;
const int m = 4;
const int n = (1 << (1 << m)) + 1;
const double pi = 3.14159265358979323846;
struct Number {
    short x[n];
    Number() {
        for (int i = 0; i < n; i++) {
            x[i] = 0;
Number operator + (const Number & a, const Number & b) {
    Number c;
    for (int i = 0; i < n; i++) {
        c.x[i] = a.x[i] + b.x[i];
    return c;
Number operator - (const Number & a, const Number & b) {
    Number c;
    for (int i = 0; i < n; i++) {
        c.x[i] = a.x[i] - b.x[i];
    return c;
Number operator * (const Number & a, const Number & b) {
    Number c;
    for (int i = 0; i < n; i++) {
        if (a.x[i] > 0) {
            for (int j = 0; j < n; j++) {
                c.x[(i + j) % n] += a.x[i] * b.x[j];
    return c;
Number operator * (const Number & a, const int & b) {
    Number c;
    for (int i = 0; i < n; i++) {
        c.x[i] += a.x[i] * b;
    return c;
bool operator == (const Number & a, const Number & b) {
    for (int i = 0; i < n; i++) {
        if (a.x[i] != b.x[i]) {
            return false;
    return true;
complex < double > omega(int k) {
    return complex < double > (cos(2 * pi * k / n), sin(2 * pi * k / n));
complex < double > calc(Number a) {
    complex < double > x = 0;
    for (int i = 0; i < n; i++) {
        x += complex < double > (a.x[i], 0) * omega(i);
    return x;
string to_cof(int x) {
    if (x == 1) {
        return "";
    } else {
        return to_string(x);
string warpper(int x) {
    if (x <= 9) {
        return to_string(x);
    } else {
        return "{" + to_string(x) + "}";
string term(int x, int y) {
    string res




    
;
    if (x > 0) {
        res = "+";
    res += to_cof(x) + "\\omega_{" + to_string(n) + "}^" + warpper(y);
    return res;
void print_LaTeX(Number x) {
    string s;
    for (int i = 0; i < n; i++) {
        if (x.x[i] != 0) {
            s += term(x.x[i], i);
    if (s.length() == 0) {
        cout << 0 << endl;
    } else {
        if (s[0] == '+') {
            s = s.substr(1, s.length() - 1);
        cout << s << endl;
void print(Number x) {
    for (int i = 0; i < n; i++) {
        printf("%d ", x.x[i]);
    printf("\n");
int pow(int a, int b) {
    int ans = 1;
    while (b != 0) {
        if ((b & 1) == 1) {
            ans = 1ll * ans * a % n;
        a = 1ll * a * a % n;
        b = b / 2;
    return ans;
int get_first(Number x) {
    for (int i = 0; i < n; i++) {
        if (x.x[i] != 0) {
            return i;
    return -1;
vector < int > get(Number x, const vector < Number > & a) {
    vector < int > res(0, a.size());
    for (int i = 0, first; i < (int)a.size(); i++) {
        first = get_first(a[i]);
        if (first != -1) {
            res.push_back(x.x[first]);
            for (int j = 0; j < n; j++) {
                if (a[i].x[j] != 0) {
                    if (x.x[j] != res[i]) {
                        printf("Error.\n");
                        return vector < int > ();
            x = x - a[i] * res[i];
    if (x == Number()) {
        return res;
    } else {
        return res;
void print(vector < int > vec) {
    for (int x : vec) {
        printf("%d ", x);
    printf("\n");
bool vis[n];
void print_LaTeX(vector < int > vec, char name) {
    bool first = true;
    for (int i = 0; i < (int)vec.size(); i++) {
        if (vec[i] > 0) {
            vis[i] = true;
            if (!first) {
                printf("+");
            } else {
                first = false;
            if (vec[i] == 1) {
                printf("%c_", name);
                cout << warpper(i);
            } else {
                printf("%d%c_", vec[i], name);
                cout << warpper(i);
    printf("\\\\");
vector < vector < int > > vec;
//int which[n];
void get_which(int i) { // 分成 2 ^ i 个组.
    vec.clear();
    for (int j = 0; j < (1 << i); j++) {
        vec.push_back(vector < int > ());
        for (int k = 0; k < (n - 1) / (1 << i); k++) {
            vec[j].push_back(pow(3, (k << i) + j));
//          which[pow(3, (k << i) + j)] = j;
vector < int > get(Number x, int i) {
    vector < int > res((1 << i), 0);
    for (int j = 0; j < (1 << i); j++) {
        res[j] = x.x[vec[j][0]];
        for (int k : vec[j]) {
            if (x.x[k] != res[j]) {
                printf("Error.");
            } else {
                x.x[k] = 0;
    for (int j = 0; j < n; j++) {
        if (x.x[j] != 0) {
            printf("Error.");
    return res;
Number get_number(int i, int j) { // 2 ^ i 个中的第 j 个.
    Number x;
    for (int k = 0; k < (n - 1) / (1 << i); k++) {
        x.x[pow(3, (k << i) + j)] = 1;
    return x;
const char * name = "zabcdefghklopqrs";
bool todo[n];
int main() {
    freopen("output.txt", "w", stdout);
    // now 表示要运算的数的层数.
    printf("$$\\begin{cases}");
	todo[0] = true;
	for (int now = (1 << m) - 1; now > 0; now--) {
		for (int i = 0; i < n; i++) {
			vis[i] = false;
		int delta = 1 << (now - 1);
		get_which(now - 1);
		for (int x = 0, y; x < delta; x++) {
			if (todo[x]) {
				y = (x + delta) % (1 << now);
				Number a = get_number(now, x) + get_number(now, y);
				cout << string() + name[now] + "_" + warpper(x) + "+" + name[now] + "_" + warpper(y) + "=";
				print_LaTeX(get(a, now - 1), name[now - 1]);
				Number b = get_number(now, x) * get_number(now, y);
				cout << string() + name[now] + "_" + warpper(x) + name[now] + "_" + warpper(y) + "=";
				print_LaTeX(get(b, now - 1), name[now - 1]);
//		printf("\n");
		for (int i = 0; i < delta / 2; i++) {
			if (vis[i] || vis[i + delta / 2]) {
//			printf("todo[%d] = true;\n", i);
				todo[i] = true;
			} else {
				todo[i] = false;
//		for (int i = 0; i < n; i++) {
//			if (vis[i]) {
//				printf("%c_", name[now - 1]);
//				cout << warpper(i) << ',';
//			}
//		}
		fprintf(stderr, "Level %d finished.\n", now);
	printf("z_0=-1\\end{cases}$$");
    return 0;
abcdefghklopqrs
123456789012345
a - 1 - 2
b - 2 - 4
c - 3 - 8
d - 4 - 16
e - 5 - 32
f - 6 - 64
g - 7 - 128
h - 8 - 256
k - 9 - 512
l - 10 - 1024
o - 11 - 2048