问题标签 [number-theory]

我一直在考虑一个数学/算法问题，希望您能就如何解决它提出意见！

如果我有一个数字（例如 479），我想将其数字或它们的组合重新组合为与原始数字匹配的数学公式。所有数字都应按其原始顺序使用，但可以组合成数字（因此，479 允许 4、7、9、47、79）但每个数字只能使用一次，所以你不能有像 4x47x9 这样的东西现在数字 4 被使用了两次。

现在举个例子来说明我的想法。这个例子在数学上是不正确的，因为我想不出一个真正有效的好例子，但它展示了输入和预期的输出。

示例输入：29485235

示例输出：2x9+48/523^5

正如我所说，我的示例没有加起来（2x9+48/523^5 不会导致 29485235）但我想知道是否有一种算法实际上可以让我找到这样一个由源数字的数字组成的公式它们的原始顺序将在计算后产生原始数字。

关于使用的数学类型，我会说括号 () 和 Add/Sub/Mul/Div/Pow/Sqrt。

关于如何做到这一点的任何想法？我的想法是通过随机地将数字分开并进行计算以希望得到匹配的结果来简单地强制它。不过一定有更好的方法吗？

编辑：如果以非原始顺序更容易，或者您有解决此问题的想法而忽略了上述一些“条件”，那么理解如何解决此类问题仍然会非常有帮助。

我正在寻找一种方法来确定方程是否存在解，例如： 3n1+4n2+5n3=456，其中n1,n2,n3是正整数。

或更一般地说：是否存在零或正整数n1,n2,n3 ... 来求解方程k1n1+k2n2+k3n3...=m其中k1,k2,k3 ... 和m是已知的正整数。

我不需要找到解决方案 - 只需确定是否存在解决方案。

编辑：

关于该算法的实际使用：

在通信库中，我想在处理消息之前根据其大小确定给定消息是否有效。例如：我知道一条消息包含零个或多个 3 字节元素、零个或多个 4 字节元素和零个或多个 5 字节元素。我收到一条 456 字节的消息，我想在进一步检查其内容之前确定其有效性。当然，消息的标题包含每种类型的元素数量，但我想通过传递类似pair<MsgType,vector<3,4,5>>.

一种方法是计算它们的gcd并检查它是否为 1。

有更快的方法吗？

我有一个系列

我想找到总和。我不能应用几何级数（GP）公式，因为结果将有分母，然后我将不得不找到可能不存在的模逆（如果分母和 m 不是互质的）。

所以我做了一个替代算法，假设这些幂将使一个长度远小于 k 的循环（因为它是一个模方程，所以我会得到类似 2,7,9,1,2,7,9 的东西， 1....）并且该循环将在上述系列中重复。因此，与其从 0 迭代到 k，我只需找到一个循环中的数字总和，然后计算上述系列中的循环数并将它们相乘。所以我首先找到i^m (mod m)这个数字，然后在每一步中一次又一次地取模，直到我再次到达第一个元素。

但是当我实际编写算法时，对于 i 的某些值，我得到了非常大的循环。因此在终止之前花费了大量时间，因此我的假设是不正确的。

那么我们还能找到其他模式吗？（基本上我不想迭代k。）所以请给我一个有效算法的想法来找到总和。

我已经有素数分解（整数），但现在我想为高斯整数实现它，但我应该怎么做呢？谢谢！

作为编程挑战的一部分，我用 C# 编写了一个程序来查找一定范围内的完美数字。但是，我意识到计算超过 10000 的完美数字时非常慢。是否有任何优化方法可以找到完美数字？我的代码如下：

我们有一些非负数。我们想找到具有最大 gcd 的对。实际上这个最大值比对更重要！例如，如果我们有：

2 4 5 15

gcd(2,4)=2

gcd(2,5)=1

gcd(2,15)=1

gcd(4,5)=1

gcd(4,15)=1

gcd(5,15)=5

答案是 5。

我正在解决 Haskell 中的一些经典问题以发展我的功能技能，并且在实施此“Programming Praxis”站点上建议的优化时遇到问题：

对于这个问题，我有三种解决方案，与第二种解决方案相比，第三种方法太慢了。有人可以建议对我的代码进行一些改进吗？

我的实现是：

假设我有一个int x = 54897旧数字索引（基于 0）和该数字的新值。获得新价值的最快方法是什么？

例子

编辑：最快，我绝对是指更快的性能。没有字符串处理。

请查看我用来查找我认为所有 Amicable Pairs (n, m), n < m, 2 <= n <= 6500 万的代码。我的代码：http ://tutoree7.pastebin.com/wKvMAWpT 。找到的对：http ://tutoree7.pastebin.com/dpEc0RbZ 。

我发现在我的笔记本电脑上每增加一百万现在需要 24 分钟。我希望有大量的 n 可以提前过滤掉。这很接近，但没有雪茄：不以“5”结尾的奇数 n。到目前为止，只有一对反例，但数量太多了：(34765731, 36939357)。那作为过滤器将过滤掉所有 n 的 40%。

我希望有一些想法，不一定是用于实现它们的 Python 代码。