编译器有趣问题求解

mathe

知乎中一个关于编译器的讨论
里面提及用程序验证\(a^3+b^3=c^3\)的无非零解问题。
题目里面写了一个无限循环，只在找到解时返回false,然后在循环外面返回true.
由于编译器优化时判断出循环不会退出，内部只有返回false,所以直接优化为返回false.

问题是题目里面使用了unsigned long long 类型，这个数据类型只有64比特，而穷举的a,b,c范围为1到\(10^9\), 实际上它们的三次方都超越了unsigned long long表达范围，
所以实际上相当于模\(2^{64}\)的计算，所以是有解的，由于穷举顺序实际相当于c最里层循环，b齐次，由于容易看出\(a=1,b=2^{22},c=1\)是一个平凡解，那么
实际上程序在经过最多\(10^9\times (2^{22}-1)+1\)次迭代后就会退出，因为它实际上求解的方程为
\(a^3+b^3 \equiv c^3 \pmod {2^{64}}, 1\le a,b,c\le 10^9\)

现在的问题是
i)这个程序最多经过多少次迭代会退出？
ii) a=c这种类型的解实际上还是一种平凡解，如何找出一个非平凡解？

wayne

这个涉及到 椭圆曲线在有限域内的解的情况

mathe

999020913^3+727187086^3=999319833^3(mod 2^64)

计算机搜索出来的几个结果
998714809^3+782888350^3=999739681^3(mod 2^64)
998104097^3+1061144^3=999534113^3(mod 2^64)
997562065^3+340359114^3=998343817^3(mod 2^64)
997547911^3+314878034^3=997947871^3(mod 2^64)
997326989^3+528914170^3=998613573^3(mod 2^64)
997085541^3+29675326^3=998270477^3(mod 2^64)

mathe

还有一个问题是max(a,b,c)最小值多少？

northwolves

mathe 发表于 2025-11-27 07:50
还有一个问题是max(a,b,c)最小值多少？

$a=b=c=2^{22}$ ?

northwolves

找到了一个小一点的解：

1. {a,b,c}={29,35,12}*2^16;Mod[a^3+b^3-c^3,2^64]

复制代码

northwolves

{2094080, 2100224, 49152}

northwolves

这个更好一点： {2096768, 2097536, 12288}

northwolves

{2097104, 2097200, 3072}

northwolves

直觉这个应该是最小的了：{2097146, 2097158, 768}