问题标签 [number-theory]

我今天早些时候得到了这个答案，关于如何将随机数种子扭曲到范围的一个边界：

但这显然会沿着指数曲线扭曲它。我怎样才能使它成为线性的？

另外，有点相关：我刚刚创建了这个简单的脚本来可视化不同类型的分布。这可能对这个问题有帮助：http: //jsfiddle.net/RTbrL/

我对 PE 在这里提出的大量问题感到惊讶。好吧，我不想要一个解决方案，但我想要一些关于问题 402正确方向的提示。

我一直无法找到 S(N) 的封闭形式解决方案。据我所知，这是一个相当大的循环。

现在我知道了更多的事情，比如 Fib(N) mod 1e9 是周期性的。看看Pisano 周期，S(N) 也有一个周期。

我想知道如何通过仅使用位移或按位运算符将一个整数除以另一个整数（均为正数）来获得余数。不应使用运算符或运算符/。%

例如，为了在除数为以下形式时获得余数，2^k以下操作产生余数。

m = Remainder

n = The number

d = The divisor

m = n & ( d - 1 )

然而，这种方法只有在d是 形式时才有效2^k。我想知道一种类似的方法来处理非2. 我目前正在解决一个问题，programming challenges并希望采用这种方法来减少程序执行时间

要找到Schnorr 群生成器，我必须找到三个数字 p、q 和 r，这样：

• p = qr + 1
• p 和 q 是素数

当 p 和 q 应该是非常大的素数时，很难找到满足所有标准的 q 和 r。我尝试使用 GNU GMP 库随机查找 q 和 r，但我在笔记本电脑上的 30 分钟内没有找到符合上述标准的数字。

有没有什么快速的方法可以找到这样的数字和 Schorr 群生成器？

谢谢！

计数小于 m, m 的数与 n 互质

我想通过(phi(n)/n)*m来做这件事，但它总是有一些小错误。

一种方法可以使用包含-排除原则，但我正在寻找比这更好的算法。

例如

给定一个整数 n 找到最小整数 x 使得 φ(x) = n。

(10^5 < n < 10^8)

我知道搜索的下限是n+1而上限是

n/((pow(e,0.577)*log(log(n))) + (3.0/(log(log(n)))))

您能否提供任何其他方法来做同样的事情。

谢谢。

更新： C(n, k) 表示Binomial Coefficient

我正在处理一个数论问题。我已经把大问题变成了一个简单的问题： 如何计算C(n,k)%3，其中 n<=10^15。大约m ( <= 10 000 )需要在1 秒内计算的数据集。

我解决它的方法是使用Lucas' theorem. 是O(m log n)。而且它的速度足以解决问题。但我想知道这个问题是否有更好的解决方案，甚至是n <= 10^100orm <= 1 000 000？

非常感谢！

抱歉，如果这个问题不适合该网站...我一直在尝试将一些 Maple 代码翻译成 Mathematica。我根本不了解 Maple，但我知道一些 Mathematica。我真的不知道我在做什么，所以我想知道是否有人可以帮助我一点：

我想我什么都懂，除了

但我不确定。提前致谢！

我们如何重新编码一组严格递增（或严格递减）的正整数 P，以减少我们集合中的整数之间可能出现的正整数的数量？

我们为什么要这样做：假设我们要对 P 进行随机抽样，但是 1.) P 太大而无法枚举，并且 2.) P 的成员以非随机方式相关，但以一种太复杂而无法抽样的方式经过。但是，当我们看到 P 的成员时，我们就知道它了。假设我们知道 P[0] 和 P[n]，但无法接受枚举所有 P 或准确理解 P 成员之间关系的想法。同样，出现在 P[0] 和 P[n] 之间的所有可能整数的数量比 P 的大小大很多倍，这使得随机抽取 P 的成员的机会非常小。

示例：设 P[0] = 2101010101 & P[n] = 505050505。现在，也许我们只对 P[0] 和 P[n] 之间具有特定质量的整数感兴趣（例如 P[x 中的所有整数） ] 总和为 Q 或更少，P 的每个成员的最大整数为 7 或更少）。因此，并非所有正整数 P[n] <= X <= P[0] 都属于 P。我感兴趣的 P 在下面的评论中讨论。

我已经尝试过：如果 P 是一个严格递减的集合，并且我们知道 P[0] 和 P[n]，那么我们可以将每个成员视为从 P[0] 中减去它。这样做可能会大大减少每个数字，并将每个成员保持为唯一的整数。对于我感兴趣的 P（如下），可以将 P 的每个减小值视为除以公分母 (9,11,99)，这会减少 P 成员之间可能的整数数量。我已经发现结合使用，这些方法将所有 P[0] <= X <= P[n] 的集合减少了几个数量级，从而有机会从所有正整数 P[n 中随机抽取 P 的成员] <= X <= P[0] 仍然很小。

注意：应该清楚，我们必须知道一些关于 P 的信息。如果我们不知道，那基本上意味着我们不知道我们在寻找什么。当我们随机抽样 P[0] 和 P[n] 之间的整数（是否重新编码）时，如果确实如此，我们需要能够说“是的，它属于 P。”。

一个好的答案可以大大增加我开发的计算算法的实际应用。评论 2 中给出了我感兴趣的那种 P 的例子。我坚持给予应有的信任。