问题标签 [diophantine]

让一般丢番图方程为： a1*x1 + a2*x2 + .... + am*xm = n ，其中 gcd(a1...am) = 1, (a1....am) >= 0

我想找到非负（x1..xm）解决方案的数量。有人可以帮我解决这个问题吗？详细的数学解释或算法将非常有帮助。

我是编程和红宝石的新手。我正在编写处理特定丢番图方程的代码（来自 MIT 开放课件问题），并且只是想看看我能用它做什么。

该代码为具有三个变量的特定线性方程生成三个数组和其中两个的散列。

这是代码：

我现在要做的是访问各个哈希配对以确保它们正确排列，但是

对任何数字返回 nil。有什么帮助吗？另外，像我这样的新手，如果有更好的方法来做我所做的任何事情，如果你让我知道，我将不胜感激。

我正在自学MIT Open Courseware Introduction to Computer Science and Programming。问题集 2涉及基于鸡块盒（6、9 或 20）计数总和的丢番图方程。

我考虑创建算法的方式就像创建一个虚拟测量棒（就像在木工店里一样），测量的大小（值）在棒上记录下来，然后转移到另一块。

如果我想象它被用在数轴上，它会指出初始值，我会在其中标记这些点，然后，我会将零点移动到它遇到的第一个标记并制作新标记，然后重复那，永远向前。

因此，采用求和公式：x=0, a=x+6, b=x+9, c=x+20，每个都附加到一个列表中，现在看起来像这样[6,9,20]：然后我想要做的是x切换到列表中的下一个最大值，为也附加到列表中的其他变量创建新值。的下一个值x是6，更改其他变量并生成如下所示的列表：[6,9,20,12,15,26]。然后，9，以此类推。

我的第一个问题是重复和导致无限循环的列表顺序。我通过添加一行来纠正这个问题，该行创建了一组再次返回列表的列表。这主要是有效的。

但是，这就是问题所在，它并没有用所有可能的值填充列表。例如，它没有将 48 放入列表中，这显然是 6 的倍数。

我的猜测是我的问题与我正在迭代一个不断被编辑和/或附加到的列表这一事实有关。

我知道有一些算法我可以使用重新设计作业，因为我做了研究，甚至看到了其他人如何为这个问题编写答案，我现在明白了，但我仍然想修复我自己的编程方式问题的解决方案。到目前为止，这是我的代码：

一个集合的 Frobenius 数存在当且仅当该集合数的 gcd 为 1。给定一组最多有 10 个元素的正整数，使得所有元素的 gcd 为 1，我们如何计算该集合的 Frobenius 数?

这是原始问题的链接：https ://icpcarchive.ecs.baylor.edu/external/62/6298.pdf Sylvester 的公式可用于查找一组 2 个元素的 Frobenius 数。

问题是：在以下等式中，x、y 和 n 是正整数。

1/x + 1/y = 1/n

对于极限 L，我们将 F(L) 定义为满足 x < y ≤ L 的解的数量。

我们可以验证 F(15) = 4 和 F(1000) = 1069。求 F(1012)。

我决定测试是否能找到 F(15)

但是列表中没有存储任何内容。

有类似的问题：检查变量是否为整数，但我看不到我的问题的答案。

我的意思是，我最近在和大数字作斗争，所以我的朋友建议我安装 Python。我今天打开它，这样我就可以计算大数并具有良好的精度，但是......如何使用这个精度？我的意思是，如果我做类似的事情pow(31,123)可以正常工作，但是如果我想检查数字是否为整数，我会得到：

我想写一个简单的循环来找到丢番图方程的一些解，我需要从非常大的数字中取平方根并检查它是否是整数，但现在我很紧张。有人可以帮助我或给我建议如何获得更好的精度吗？

例子：

例如：$ 2x^2 = 1 + y^31 $，其中 x,y 是整数。我的想法是制作循环，在其中增加 y（从 1 开始），加 1，除以 2，取平方根，然后它必须是整数才能满足方程。这就是我需要它的原因。

我在 Maxima 中定义了一个扩展的欧几里得算法

为了解决a + b = c形式的线性丢番图方程，其中gcd（a，b）= 1，但是如果ab = c我得到-1由除数算法返回，但gcd（a，-b）为前。我的算法是错误的，还是可以用于 ab=c？

伊恩

I have a program that takes user input in the form of an integer, lets call it k. Three other numbers are known, a,b and c. My task is to find all positive integer solutions {x,y,z} such that ax + by + cz = k. I wrote a method that I call on objects that have a,b and c built in. There is an additional constraint that says that x + y + z cannot be greater than a known integer p.

This works when k is somewhat small (<100000), although as it exceeds 3 digits the interpreter freezes for a couple of seconds as it does its calculations, but eventually it does what its supposed to.

My problem is that if k is larger, the amount of combinations that have to be checked becomes too many to handle for the python interpreter.

So I was thinking that maybe a way of avoiding these crashes is to, instead of the program finding all solutions and adding them all at once, to make the program find each solution and add it one-by-one to the listbox, so as to avoid the computer storing to much information in its RAM before its used. However, with tkinters .insert method seeming like the only way of appending the listbox with info, I don't know how to do this.

Any help would be greatly appreciated!

所以我正在解决一个需要我做的问题：

使用 3 个嵌套循环生成 (F^5-E^5-D^5) 的每个组合存储所有这些组合。然后使用 3 个不同的嵌套循环生成 (A^5+B^5+C^5) 的每个组合并存储所有这些值。其中 0 < A ≤ B ≤ C ≤ D ≤ E ≤ F ≤ N

我一直在关注这个线程，这正是我想要完成的。

我遇到的问题是我的代码设置方式，每次循环再次执行时，我存储值的数组都会被覆盖。

数组需要多长时间来存储值（可能是 N^3）？我怎么能在不覆盖的情况下做到这一点？

到目前为止，这是我的代码：

我有以下问题：

给定一组变量和，例如 { a + b, b + c, c + d, a + a + d, b }，找到变量的正整数值，使得所有和都不同并且最大和一样小尽可能。

是否有一种算法可以找到或近似解决此类问题？