java - 在 Java 中生成丢番图方程的值？

Question

我有一个程序要编码，它将求解 5-1 五阶丢番图方程，基本上是 A^5 + B^5 + C^5 + D^5 + E^5 = F^5，其中 0 < A <= B <= C <= D <= E <= F <= N。我要实现它的方式是预先计算给定的 N 值，然后将其存储到数组中。例如，如果 N 为 100，它将把 1 到 100 之间的值存储在数组中。

然后，我将计算第一组 A^5 + B^5 + C^5 和第二组 F^5 - (D^5 + E^5) 的值，并比较以下值将第一组转到第二组，看看它们是否匹配。如果匹配，则找到解决方案。

我的问题是，如何使用 1 到 N 之间的值数组来计算这两个组的所有可能值？我已经有了这个想法，但是将其编码出来，我不知道如何实现它。有人可以给我一些提示吗？我并不是在寻求如何编码的解决方案，我只是想要一些技巧/提示，它们可以帮助我更好地理解编码过程。谢谢!

Answer 1

我肯定会从计算 1 到 N 中每个数字的所有 5 阶值开始然后我将从边 F^5 - (A^5 + B^5 + C^5 + D^5 + E^5 ) 开始，

1)外循环，生成F^5的值从尽可能高的值开始幸运的是我们知道 F 的最小值是 72。兰德和帕金 (1967)

其余循环从最低值开始，

2)第二个循环，生成E^5的值

3)第三个循环，生成 D^5 的值，测试 F^5 的值 - (D^5 + E^5) 如果为负，则可以打破此循环(但不能打破外循环

继续进行 3 个剩余循环以获得 3 个剩余值。如果你的等式每个循环将有越来越少的值来测试。因为只要等式变为负数或者达到已经使用过的数字，我们就可以停止

方程为零的任何解都是解。

时间分析很困难，如果 N^2，前 2 个循环将产生结果，但其余 4 个循环会小得多，甚至可能每个循环都为 logn 时间，希望在一起为 nlogn 时间

我用 n=600 进行了测试。其最大解为
218^5 + 276^5 + 385^5 + 409^5 + 495^5 = 553^5一个 N^6 方程需要 4E16 步才能得到这个解，而我的方程需要 2E15 步或者 5% 的时间才能得到这个解。

不确定这是否会将其降低到 n^3logn，但它可以通过跳过大量不正确的解决方案让您更接近。