问题标签 [diophantine]

我最近对 ​​Project Euler 非常上瘾，接下来我正在尝试做这个！我已经开始对其进行一些分析，并且已经大大减少了问题。这是我的工作：

A = pqr 和

1/A = 1/p + 1/q + 1/r 所以 pqr/A = pq + pr + qr

由于第一个方程：

pq+pr+qr = 1

由于 p、q 和 r 中的两个必须是负数，我们可以将方程简化为：

abc 其中 ab = ac+bc+1

求解 c 我们得到：

ab-1 = (a+b)c

c = (ab-1)/(a+b)

---

这意味着我们需要找到 a 和 b ：

ab = 1 (mod a+b)

然后我们的 A 值与那些 a 和 b 是：

A = abc = ab(ab-1)/(a+b)

对不起，如果这是很多数学！但现在我们要处理的只是一个条件和两个方程。现在，因为我需要找到写为 ab(ab-1)/(a+b) 且 ab = 1 (mod a+b) 的第 150,000 个最小整数，所以理想情况下我想搜索 A 的 (a, b)尽可能小。

为方便起见，我假设 a < b 并且我还注意到 gcd(a, b) = 1。

我的第一个实现是直截了当的，甚至可以足够快地找到 150,000 个解决方案。但是，找到 150,000 个最小的解决方案需要很长时间。无论如何，这是代码：

我的下一个想法是使用 Stern-Brocot 树，但这太慢了，无法找到解决方案。我的最终算法是使用中国剩余定理来检查 a+b 的不同值是否产生解决方案。该代码很复杂，虽然速度更快，但还不够快......

所以我完全没有想法！有人有什么想法吗？

我决定接下来解决 Project Euler问题 233，但我遇到了一些重大问题！我已经做了一些分析并取得了一些相当不错的进展，但我现在陷入了困境。这是我的工作：

引理 1：由于圆穿过 4 个角点，因此任何 n 至少有 4 个解。但是对于圆周上的每个点，通过反射发现了另外 7 个点。因此总是有 8k+4 个格点。

引理 2：圆的半径为 (√2)n，圆心为 (n/2, n/2)，因此其方程为 (xn/2)^2 + (yn/2)^2 = [n/√2]^ 2. 这减少到 x^2+y^2 = n(x+y)。

引理 3：如果 x^2+y^2 = n(x+y) 的解写成 (x, y, z)，则另一个解是 (kx, ky, kz)。证明是：

这与我对这种思路所做的一样多 - 我看不到从那里去的任何地方，但它被包括在内，因为它可能很有用。

我的下一个想法是移动圆心。将有相同数量的解决方案在任何维度上移动一个整数。所以当n/2为整数时，所以n=2k，x^2+y^2 = 2*k^2。而且事实证明，这个方程的解与方程 x^2+y^2=k^2 的解一样多（参见 Sloane A046109）。

这也提供了一种通过A046080计算任何 n 的解决方案数量的简单方法。如果 4k+1 形式的 n 中素数的幂是 f[0]...f[m]，则解的数量是 4*product(2f[i]+1 | i in [0.. .m]）。

这让我可以向后工作： 4.product(2f[i]+1 | i in [0...m]) = 420, 所以 product(2f[i]+1 | i in [0...m] ) = 105 = 3*5*7。我能够想出这个程序，我认为它可以找到所有 n 的总和，形式为 2k 且小于 10^11，它有 420 个圆格点。答案（我希望！）是 257199853438240692。

这是C程序：

我们只需要将具有 420 个圆格点且形式为 2k+1 的 n 的值相加！但是，这似乎比 n=2k 更难，而且我看不到任何方法。我也有点不确定我对偶数 n 的回答是否正确，因为该方法非常复杂......有人可以确认吗？有没有一种简洁的方法而不涉及不同地对待不同的 n？

我完全没主意了！

我最感兴趣的是我如何处理 N=2k+1，因为当 N=2k 时，我可以按照 John Feminella 的建议进行操作。

是否有一个相当快的算法来解决线性丢番图不等式系统？

现在我已经完成了查找 23 组 xyz 值满足条件 x^3+y^3=1+z^3 & x

但是我的代码效率很低，有人可以帮我解决这个问题吗？

所以我有一组有界丢番图方程，它们指定平面上的线。我想让mathematica 绘制这两个方程的交集，这样我就可以看到它们的样子。

到目前为止，我有类似的东西：

求解[0 < x - y < 3 && -1 < 2 x - y < 2, {x, y}, 整数]

它返回一些结构，如：

{{x -> -2, y -> -4}, {x -> -1, y -> -3}, {x -> -1, y -> -2}, {x -> 0, y -> -1}}

但是我现在怎样才能让mathematica 绘制这个图，以便我可以看到生成的形状。最好我希望情节将每个“点”视为一个 1x1 正方形。

另外，我想知道是否有更好的方法来做这些事情。谢谢。

在我的研究中，我遇到了一个线性丢番图方程组。

我找到了几篇关于该主题的研究论文，但在我开始自己创建求解器之前，我想知道是否有人知道（轻量级）C++ 数学库，它可以解决这样的系统。

我对这些问题在数学和编程上都是新手。如果有人可以建议使用可以解决以下问题的 c++ 库，我将不胜感激。

给定常量：

{x_1, ..., x_n}, {y_1, ..., y_n}, {z_1, ..., z_n}, C, & variables {q_1, ..., q_n}

最大化：sum(i = 1..n} q_i*x_i

受制于：C - sum(i = 1..n){ sum(j = 1..q_i) [y_i + (j-1)*z_i ] } >= 0 AND q_i >= 0

所有常量都是大于零的整数。q_i's也是整数。

所以我试图解决{q_1, ..., q_n}

我正在尝试为给定的 H 生成以下方程的所有解。

随着 H=4 ：

对于我的问题，总是有 4 个方程需要求解（独立于其他方程）。总共有 2^(H-1) 个解。对于上一个，以下是解决方案：

这是解决问题的R算法。

但是，该算法进行的计算超出了需要。我相信有可能走得更快。我的意思是不生成总和为 > H 的排列

对于给定的 H 有更好的算法的想法吗？

我是 Python 的初学者，并尝试使用MIT 6.00，提供的页面是作业页面。

我在作业 2中，我必须找到丢番图方程的解，我的数学真的不是很好，所以我试图尽可能多地理解它的作用，并想出一个解决方案。

这就是我要做的：

作业指出有 的解决方案50, 51, 52, 53, 54, and 55，但不幸的是，脚本只能获得 的解决方案50, 53 and 55。

如果有人解释我的代码有什么问题，或者我根本不理解丢番图方程，我将非常感激，请告诉我这是怎么回事以及如何找到解决方案，因为我无法得到作业解释进入我的脑海。

谢谢。

我有一个程序来编写代码，它将求解一个 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 之间的值数组来计算两组的所有可能值？我有这个想法，但是把它编码出来，我不知道如何处理它。谁能给我一些提示？我不是在询问如何编码的解决方案，我只是想要一些可以帮助我更好地理解编码过程的提示/提示。谢谢！