数论¶
Ntheory 类参考¶
- class sympy.ntheory.generate.Sieve(sieve_interval=1000000)[源代码][源代码]¶
一个质数列表，实现为一个动态增长的埃拉托色尼筛法。当请求查找一个尚未被筛分的奇数时，筛法会自动扩展到该数。实现细节限制了质数的数量为
2^32-1。方法
extend(n)将筛子扩展到覆盖所有小于等于 n 的素数。
extend_to_no(i)扩展以包含第i个素数。
mobiusrange(a, b)生成范围 [a, b) 内的所有 mobius 数。
primerange(a[, b])生成范围 [2, a) 或 [a, b) 内的所有质数。
search(n)返回界定 n 的素数的索引 i, j。
totientrange(a, b)生成范围 [a, b) 内的所有欧拉函数数。
示例
>>> from sympy import sieve >>> sieve._reset() # this line for doctest only >>> 25 in sieve False >>> sieve._list array('L', [2, 3, 5, 7, 11, 13, 17, 19, 23])
- extend(n)[源代码][源代码]¶
将筛子扩展到覆盖所有小于等于 n 的素数。
示例
>>> from sympy import sieve >>> sieve._reset() # this line for doctest only >>> sieve.extend(30) >>> sieve[10] == 29 True
- extend_to_no(i)[源代码][源代码]¶
扩展以包含第i个素数。
- 参数:
- i整数
注释
如果列表太短，它会被延长50%，因此它很可能会比要求的长。
示例
>>> from sympy import sieve >>> sieve._reset() # this line for doctest only >>> sieve.extend_to_no(9) >>> sieve._list array('L', [2, 3, 5, 7, 11, 13, 17, 19, 23])
- mobiusrange(a, b)[源代码][源代码]¶
生成范围 [a, b) 内的所有 mobius 数。
- 参数:
- a整数
范围中的第一个数字
- b整数
范围外的第一个数字
示例
>>> from sympy import sieve >>> print([i for i in sieve.mobiusrange(7, 18)]) [-1, 0, 0, 1, -1, 0, -1, 1, 1, 0, -1]
- primerange(a, b=None)[源代码][源代码]¶
生成范围 [2, a) 或 [a, b) 内的所有质数。
示例
>>> from sympy import sieve, prime
所有小于19的质数：
>>> print([i for i in sieve.primerange(19)]) [2, 3, 5, 7, 11, 13, 17]
所有大于或等于7且小于19的质数：
>>> print([i for i in sieve.primerange(7, 19)]) [7, 11, 13, 17]
所有素数，直到第10个素数
>>> list(sieve.primerange(prime(10) + 1)) [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Ntheory 函数参考¶
- sympy.ntheory.generate.prime(nth)[源代码][源代码]¶
返回第 n 个质数，质数的索引从 1 开始：prime(1) = 2, prime(2) = 3，等等。
- 参数:
- 第n个整数
要返回的素数的位置（必须是一个正整数）。
- 返回:
- 整数
第 n 个质数。
参见
sympy.ntheory.primetest.isprime测试一个数是否为质数。
primerange生成给定范围内的所有素数。
primepi返回小于或等于给定数字的素数数量。
参考文献
[1][2][3]示例
>>> from sympy import prime >>> prime(10) 29 >>> prime(1) 2 >>> prime(100000) 1299709
- sympy.ntheory.generate.primepi(n)[源代码][源代码]¶
表示素数计数函数 pi(n) = 小于或等于 n 的素数的数量。
自 1.13 版本弃用:
primepi函数已被弃用。请改用sympy.functions.combinatorial.numbers.primepi。更多信息请参阅其文档。详情请参阅 将符号函数从 ntheory 移动到 functions。算法描述：
在筛法中，我们移除除 p 本身外的所有素数 p 的倍数。
设 phi(i,j) 为从不超过 j 的素数筛选后，剩余的 2 <= k <= i 的整数数量。显然，pi(n) = phi(n, sqrt(n))
如果 j 不是质数，phi(i,j) = phi(i, j - 1)
如果 j 是质数，我们移除所有最小质因数为 j 的数（除了 j 本身）。
设 \(x= j \times a\) 为这样的一个数，其中 \(2 \le a \le i / j\)。现在，在筛除 \(\le j - 1\) 的质数后，a 必须保留（因为 x 和 a 没有 \(\le j - 1\) 的质因数）。显然，在筛除 \(\le j - 1\) 的质数后，有 phi(i / j, j - 1) 个这样的 a 保留下来。
现在，如果 a 是一个小于等于 j - 1 的质数，\(x= j imes a\) 的最小质因数 = a，并且已经被移除（通过从 a 筛选）。因此，我们不需要再次移除它。（注意：这样的 x 将有 pi(j - 1) 个）
因此，需要移除的 x 的数量为：phi(i / j, j - 1) - phi(j - 1, j - 1) （注意 pi(j - 1) = phi(j - 1, j - 1)）
\(\Rightarrow\) phi(i,j) = phi(i, j - 1) - phi(i / j, j - 1) + phi(j - 1, j - 1)
因此，递归被使用并实现为 dp：
phi(a, b) = phi(a, b - 1), 如果 b 不是质数 phi(a, b) = phi(a, b-1)-phi(a / b, b-1) + phi(b-1, b-1), 如果 b 是质数
显然，a 总是取 floor(n / k) 的形式，最多可以取 \(2\sqrt{n}\) 个值。维护两个数组 arr1 和 arr2，其中 arr1[i] = phi(i, j)，arr2[i] = phi(n // i, j)
最终答案是 arr2[1]
参见
sympy.ntheory.primetest.isprime测试 n 是否为质数
primerange生成给定范围内的所有质数
prime返回第 n 个质数
示例
>>> from sympy import primepi, prime, prevprime, isprime >>> primepi(25) 9
所以有9个小于或等于25的质数。25是质数吗？
>>> isprime(25) False
它不是。因此，小于25的第一个质数必须是第9个质数：
>>> prevprime(25) == prime(9) True
- sympy.ntheory.generate.nextprime(n, ith=1)[源代码][源代码]¶
返回大于 n 的第 i 个质数。
- 参数:
- n整数
- ith正整数
- 返回:
- 整数返回大于 n 的第 i 个质数
- Raises:
- ValueError
如果
ith <= 0。如果n或ith不是整数。
参见
prevprime返回小于 n 的最大质数
primerange生成给定范围内的所有质数
注释
潜在的素数位于 6*j +/- 1。这一特性在搜索过程中被使用。
>>> from sympy import nextprime >>> [(i, nextprime(i)) for i in range(10, 15)] [(10, 11), (11, 13), (12, 13), (13, 17), (14, 17)] >>> nextprime(2, ith=2) # the 2nd prime after 2 5
- sympy.ntheory.generate.prevprime(n)[源代码][源代码]¶
返回小于 n 的最大质数。
参见
nextprime返回大于 n 的第 i 个质数
primerange生成给定范围内的所有素数
注释
潜在的素数位于 6*j +/- 1。这一特性在搜索过程中被使用。
>>> from sympy import prevprime >>> [(i, prevprime(i)) for i in range(10, 15)] [(10, 7), (11, 7), (12, 11), (13, 11), (14, 13)]
- sympy.ntheory.generate.primerange(a, b=None)[源代码][源代码]¶
生成范围 [2, a) 或 [a, b) 内的所有素数列表。
如果范围存在于默认筛子中，值将从那里返回；否则，值将被返回，但不会修改筛子。
参见
注释
关于在给定范围内素数出现的著名猜想有 [1]：
- 孪生素数：尽管通常不是，但以下将给出2个素数
- 无限次：
primerange(6*n - 1, 6*n + 2)
- 勒让德的：以下总是至少产生一个素数
primerange(n**2, (n+1)**2+1)
- 伯特兰的（已证明）：在范围内总是存在一个质数。
primerange(n, 2*n)
- Brocard’s：在这个范围内至少有四个质数。
primerange(prime(n)**2, prime(n+1)**2)
素数之间的平均间隔是 log(n) [2]；素数之间的间隔可以是任意大的，因为合数序列可以是任意大的，例如序列 n! + 2, n! + 3 … n! + n 中的所有数都是合数。
参考文献
示例
>>> from sympy import primerange, prime
所有小于19的质数：
>>> list(primerange(19)) [2, 3, 5, 7, 11, 13, 17]
所有大于或等于7且小于19的质数：
>>> list(primerange(7, 19)) [7, 11, 13, 17]
所有素数，直到第10个素数
>>> list(primerange(prime(10) + 1)) [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Sieve 方法，primerange，通常更快，但它会占用更多内存，因为筛子存储了值。默认的 Sieve 实例，名为 sieve，可以使用：
>>> from sympy import sieve >>> list(sieve.primerange(1, 30)) [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
- sympy.ntheory.generate.randprime(a, b)[源代码][源代码]¶
返回范围 [a, b) 内的一个随机素数。
伯特兰的假设保证了对于 a > 1，randprime(a, 2*a) 总是会成功。
请注意，由于实现上的困难，所选择的质数并非均匀随机。例如，在范围 [112, 128) 内有两个质数，
113和127，但randprime(112, 128)返回127的概率为 15/17。参见
primerange生成给定范围内的所有质数
参考文献
示例
>>> from sympy import randprime, isprime >>> randprime(1, 30) 13 >>> isprime(randprime(1, 30)) True
- sympy.ntheory.generate.primorial(n, nth=True)[源代码][源代码]¶
返回前 n 个质数的乘积（默认）或小于等于 n 的质数（当
nth=False时）。参见
primerange生成给定范围内的所有质数
示例
>>> from sympy.ntheory.generate import primorial, primerange >>> from sympy import factorint, Mul, primefactors, sqrt >>> primorial(4) # the first 4 primes are 2, 3, 5, 7 210 >>> primorial(4, nth=False) # primes <= 4 are 2 and 3 6 >>> primorial(1) 2 >>> primorial(1, nth=False) 1 >>> primorial(sqrt(101), nth=False) 210
有人可能会认为质数是无限的，因为如果你取一组质数并将它们相乘（例如质数积），然后加或减1，结果不能被任何原始因子整除，因此要么1个或更多新的质数必须整除这个质数积。
在这种情况下，这个数字本身就是一个新的质数：
>>> factorint(primorial(4) + 1) {211: 1}
在这种情况下，两个新的质数是因子：
>>> factorint(primorial(4) - 1) {11: 1, 19: 1}
这里，得到了一些比乘在一起的质数更小和更大的质数：
>>> p = list(primerange(10, 20)) >>> sorted(set(primefactors(Mul(*p) + 1)).difference(set(p))) [2, 5, 31, 149]
- sympy.ntheory.generate.cycle_length(f, x0, nmax=None, values=False)[源代码][源代码]¶
对于给定的迭代序列，返回一个生成器，该生成器给出迭代循环的长度（lambda）和循环开始前的项的长度（mu）；如果
values为 True，则将返回序列的项。序列从值x0开始。注意：可能会返回超过第一个 lambda + mu 项，这是使用 Brent 方法进行循环检测的成本；然而，通常计算的项数会比通过使用 Floyd 方法确定正确结束点所计算的项数要少。
>>> from sympy.ntheory.generate import cycle_length
这将产生 i 的连续值 <– func(i):
>>> def gen(func, i): ... while 1: ... yield i ... i = func(i) ...
定义了一个函数：
>>> func = lambda i: (i**2 + 1) % 51
并且给定一个种子为4，以及计算出的mu和lambda项：
>>> next(cycle_length(func, 4)) (6, 3)
我们可以通过查看输出来了解其含义：
>>> iter = cycle_length(func, 4, values=True) >>> list(iter) [4, 17, 35, 2, 5, 26, 14, 44, 50, 2, 5, 26, 14]
前3个值之后有6个重复值。
如果一个序列被怀疑可能比你希望的更长，可以使用
nmax提前退出（并且 mu 将返回为 None）：>>> next(cycle_length(func, 4, nmax = 4)) (4, None) >>> list(cycle_length(func, 4, nmax = 4, values=True)) [4, 17, 35, 2]
- sympy.ntheory.generate.composite(nth)[源代码][源代码]¶
返回第 n 个合数，合数的索引为 composite(1) = 4, composite(2) = 6, 等等…
参见
sympy.ntheory.primetest.isprime测试 n 是否为质数
primerange生成给定范围内的所有质数
primepi返回小于或等于 n 的素数个数
prime返回第 n 个质数
compositepi返回小于或等于 n 的正合数的数量
示例
>>> from sympy import composite >>> composite(36) 52 >>> composite(1) 4 >>> composite(17737) 20000
- sympy.ntheory.generate.compositepi(n)[源代码][源代码]¶
返回小于或等于 n 的正合数的数量。第一个正合数是 4，即 compositepi(4) = 1。
参见
sympy.ntheory.primetest.isprime测试 n 是否为质数
primerange生成给定范围内的所有质数
prime返回第 n 个质数
primepi返回小于或等于 n 的素数个数
composite返回第 n 个合数
示例
>>> from sympy import compositepi >>> compositepi(25) 15 >>> compositepi(1000) 831
- sympy.ntheory.factor_.smoothness(n)[源代码][源代码]¶
返回 n 的 B-光滑和 B-幂光滑值。
n 的平滑度是 n 的最大质因数；幂平滑度是最大除数乘以其重数。
示例
>>> from sympy.ntheory.factor_ import smoothness >>> smoothness(2**7*3**2) (3, 128) >>> smoothness(2**4*13) (13, 16) >>> smoothness(2) (2, 2)
- sympy.ntheory.factor_.smoothness_p(n, m=-1, power=0, visual=None)[源代码][源代码]¶
返回一个列表 [m, (p, (M, sm(p + m), psm(p + m)))…] 其中：
p**M 是 n 的 p 进制除数
sm(p + m) 是 p + m 的平滑度（默认情况下 m = -1）
psm(p + m) 是 p + m 的功率平滑度
列表根据平滑度（默认）或根据功率平滑度（如果 power=1）进行排序。
数字在因子左边（m = -1）或右边（m = 1）的平滑度决定了从 p +/- 1 型因式分解方法中得到的结果。
>>> from sympy.ntheory.factor_ import smoothness_p, factorint >>> smoothness_p(10431, m=1) (1, [(3, (2, 2, 4)), (19, (1, 5, 5)), (61, (1, 31, 31))]) >>> smoothness_p(10431) (-1, [(3, (2, 2, 2)), (19, (1, 3, 9)), (61, (1, 5, 5))]) >>> smoothness_p(10431, power=1) (-1, [(3, (2, 2, 2)), (61, (1, 5, 5)), (19, (1, 3, 9))])
如果 visual=True，则将返回一个带注释的字符串：
>>> print(smoothness_p(21477639576571, visual=1)) p**i=4410317**1 has p-1 B=1787, B-pow=1787 p**i=4869863**1 has p-1 B=2434931, B-pow=2434931
这个字符串也可以直接从一个因式分解字典生成，反之亦然：
>>> factorint(17*9) {3: 2, 17: 1} >>> smoothness_p(_) 'p**i=3**2 has p-1 B=2, B-pow=2\np**i=17**1 has p-1 B=2, B-pow=16' >>> smoothness_p(_) {3: 2, 17: 1}
输出逻辑的表格如下：
视觉
toctree是一个 reStructuredText 指令 ，这是一个非常多功能的标记。指令可以有参数、选项和内容。真
假
其他
dict
str
元组
str
str
str
元组
dict
元组
str
元组
str
n
str
元组
元组
mul
str
元组
元组
参见
- sympy.ntheory.factor_.multiplicity(p, n)[源代码][源代码]¶
找到使得 p**m 整除 n 的最大整数 m。
参见
trailing
示例
>>> from sympy import multiplicity, Rational >>> [multiplicity(5, n) for n in [8, 5, 25, 125, 250]] [0, 1, 2, 3, 3] >>> multiplicity(3, Rational(1, 9)) -2
注意：在检查一个大阶乘中某个数的重数时，最有效的方法是将其作为未计算的阶乘发送，或者直接调用
multiplicity_in_factorial：>>> from sympy.ntheory import multiplicity_in_factorial >>> from sympy import factorial >>> p = factorial(25) >>> n = 2**100 >>> nfac = factorial(n, evaluate=False) >>> multiplicity(p, nfac) 52818775009509558395695966887 >>> _ == multiplicity_in_factorial(p, n) True
- sympy.ntheory.factor_.perfect_power(
- n,
- candidates=None,
- big=True,
- factor=True,
返回
(b, e)使得n==b**e如果n是一个唯一的完美幂且e > 1，否则返回False``（例如，1 不是一个完美幂）。如果 ``n不是 Rational，则引发 ValueError。默认情况下，基数会被递归分解，并收集指数，以寻求尽可能大的
e。如果big=False，则会选择尽可能小的 ``e``（因此是质数）。如果
factor=True，则尝试对n进行同时因式分解，因为找到一个因子表明n的唯一可能根。这是默认设置，因为在搜索完美幂的过程中只会测试几个小因子。candidates的使用主要是为了内部使用；如果提供，如果n不能写成以其中一个候选数为指数的幂，并且不会尝试因式分解（除了测试2的因子），则会返回 False。注释
要知道一个整数是否是2的完美幂，请使用
>>> is2pow = lambda n: bool(n and not n & (n - 1)) >>> [(i, is2pow(i)) for i in range(5)] [(0, False), (1, True), (2, True), (3, False), (4, True)]
不需要提供
candidates。当提供时，将假定它们是整数。第一个大于计算出的最大可能指数的值将表示该例程失败。>>> perfect_power(3**8, [9]) False >>> perfect_power(3**8, [2, 4, 8]) (3, 8) >>> perfect_power(3**8, [4, 8], big=False) (9, 4)
示例
>>> from sympy import perfect_power, Rational >>> perfect_power(16) (2, 4) >>> perfect_power(16, big=False) (4, 2)
负数只能有奇数的完全幂：
>>> perfect_power(-4) False >>> perfect_power(-8) (-2, 3)
有理数也被识别：
>>> perfect_power(Rational(1, 2)**3) (1/2, 3) >>> perfect_power(Rational(-3, 2)**3) (-3/2, 3)
- sympy.ntheory.factor_.pollard_rho(
- n,
- s=2,
- a=1,
- retries=5,
- seed=1234,
- max_steps=None,
- F=None,
使用 Pollard 的 rho 方法尝试提取
n的非平凡因子。返回的因子可能是一个合数。如果未找到因子，则返回None。该算法通过生成器函数生成 x 的伪随机值，用 F(x) 替换 x。如果未提供 F，则使用函数 x**2 +
a。提供给 F(x) 的第一个值是s。如果失败（如果retries大于 0），将提供新的a和s；如果提供了 F，则a将被忽略。这类函数生成的数字序列通常会有一个趋近某个数字的过程，然后循环回到该数字并开始重复该序列，例如 1, 2, 3, 4, 5, 3, 4, 5 – 这种领导和循环看起来有点像希腊字母 rho，因此得名 ‘rho’。
对于给定的函数，可以获得非常不同的 leader-loop 值，因此允许重试是一个好主意：
>>> from sympy.ntheory.generate import cycle_length >>> n = 16843009 >>> F = lambda x:(2048*pow(x, 2, n) + 32767) % n >>> for s in range(5): ... print('loop length = %4i; leader length = %3i' % next(cycle_length(F, s))) ... loop length = 2489; leader length = 43 loop length = 78; leader length = 121 loop length = 1482; leader length = 100 loop length = 1482; leader length = 286 loop length = 1482; leader length = 101
这是一个明确的例子，其中有一个包含三个元素的前导部分，接着是一组重复的三个数字（11, 14, 4）：
>>> x=2 >>> for i in range(9): ... print(x) ... x=(x**2+12)%17 ... 2 16 13 11 14 4 11 14 4 >>> next(cycle_length(lambda x: (x**2+12)%17, 2)) (3, 3) >>> list(cycle_length(lambda x: (x**2+12)%17, 2, values=True)) [2, 16, 13, 11, 14, 4]
与其检查所有生成的值与 n 的 gcd 的差异，不如只检查第 k 和 2*k 个数字，例如第 1 和第 2 个，第 2 和第 4 个，第 3 和第 6 个，直到检测到循环已被遍历。循环可能在 rho 找到一个因子或报告失败之前有数千步长。如果指定了
max_steps，则在指定数量的步骤后取消迭代并失败。参考文献
[1]Richard Crandall 和 Carl Pomerance (2005)，《素数：计算视角》，Springer，第二版，229-231
示例
>>> from sympy import pollard_rho >>> n=16843009 >>> F=lambda x:(2048*pow(x,2,n) + 32767) % n >>> pollard_rho(n, F=F) 257
使用默认设置，参数值为
a且不重试：>>> pollard_rho(n, a=n-2, retries=0)
如果重试次数大于0，那么当为a生成新值时，问题可能会自行纠正。
>>> pollard_rho(n, a=n-2, retries=1) 257
- sympy.ntheory.factor_.pollard_pm1(n, B=10, a=2, retries=0, seed=1234)[源代码][源代码]¶
使用 Pollard 的 p-1 方法尝试提取
n的非平凡因子。返回一个除数（可能是合数）或None。a的值是在测试 gcd(a**M - 1, n) 中使用的基数。默认值为 2。如果retries> 0，那么在第一次尝试后如果没有找到因子，将随机生成一个新的a``（使用 ``seed）并重复该过程。注意：M 的值是 lcm(1..B) = reduce(ilcm, range(2, B + 1))。
搜索在偶数旁边的因数，这些因数的幂平滑度小于
B。选择一个较大的 B 会增加找到较大因数的可能性，但需要更长的时间。是否找到 n 的因数取决于a和紧邻因数 p 的偶数的幂平滑度（因此得名 p - 1）。尽管关于什么是好的
a的讨论有些描述难以解释。在下面引用的 modular.math 网站上提到，如果 gcd(a**M - 1, n) = N，那么对于 N 的每个素数幂除数，a**M % q**r 都是 1。但请考虑以下内容：>>> from sympy.ntheory.factor_ import smoothness_p, pollard_pm1 >>> n=257*1009 >>> smoothness_p(n) (-1, [(257, (1, 2, 256)), (1009, (1, 7, 16))])
因此，我们应该（并且可以）找到一个 B=16 的根：
>>> pollard_pm1(n, B=16, a=3) 1009
如果我们尝试将 B 增加到 256，我们发现它不起作用：
>>> pollard_pm1(n, B=256) >>>
但如果
a的值改变，我们发现只有 257 的倍数有效，例如：>>> pollard_pm1(n, B=256, a=257) 1009
检查不同的
a值显示，所有不起作用的值的 gcd 值都不等于n，而是等于其中一个因子：>>> from sympy import ilcm, igcd, factorint, Pow >>> M = 1 >>> for i in range(2, 256): ... M = ilcm(M, i) ... >>> set([igcd(pow(a, M, n) - 1, n) for a in range(2, 256) if ... igcd(pow(a, M, n) - 1, n) != n]) {1009}
但是，对于 n 的每个除数，aM % d 是否都等于 1？
>>> aM = pow(255, M, n) >>> [(d, aM%Pow(*d.args)) for d in factorint(n, visual=True).args] [(257**1, 1), (1009**1, 1)]
不，只有一个。所以也许原则是，对于给定的 B 值，将找到一个根，前提是：
根旁边的 p - 1 值的平滑度不超过 B
a**M % p != 1 对于 n 的任何除数。
通过尝试多个
a，有可能其中一个会产生一个因子。参考文献
[1]Richard Crandall & Carl Pomerance (2005), “素数：计算视角”, Springer, 第二版, 236-238
示例
使用默认的平滑边界，这个数字无法被破解：
>>> from sympy.ntheory import pollard_pm1 >>> pollard_pm1(21477639576571)
增加平滑度界限有助于：
>>> pollard_pm1(21477639576571, B=2000) 4410317
观察这个数字的因子的平滑度，我们发现：
>>> from sympy.ntheory.factor_ import smoothness_p, factorint >>> print(smoothness_p(21477639576571, visual=1)) p**i=4410317**1 has p-1 B=1787, B-pow=1787 p**i=4869863**1 has p-1 B=2434931, B-pow=2434931
对于除数的 p - 1 因式分解，B 和 B-pow 是相同的，因为这些因式分解有一个非常大的质因数：
>>> factorint(4410317 - 1) {2: 2, 617: 1, 1787: 1} >>> factorint(4869863-1) {2: 1, 2434931: 1}
请注意，直到 B 达到 1787 的 B-pow 值，这个数字才被破解；
>>> pollard_pm1(21477639576571, B=1786) >>> pollard_pm1(21477639576571, B=1787) 4410317
B 值与除数旁边的数字的因子有关，而不是除数本身。最坏的情况是，因子 p 旁边的数字有一个大的素数除数或是一个完全幂。如果这些条件适用，那么幂平滑度将大约是 p/2 或 p。更现实的情况是，p 旁边会有一个大的素数因子，需要一个大约 p/2 的 B 值。尽管可能已经搜索到这个级别的素数，但 p/2 是 p - 1 的因子，这是我们不知道的。下面的 modular.math 参考文献指出，10**15 到 15**15 + 10**4 范围内的数字中有 15% 是 10**6 幂平滑的，因此在那个范围内，B 为 10**6 将失败 85% 的时间。从 10**8 到 10**8 + 10**3，百分比几乎相反…但在那个范围内，简单的试验除法非常快。
- sympy.ntheory.factor_.factorint(
- n,
- limit=None,
- use_trial=True,
- use_rho=True,
- use_pm1=True,
- use_ecm=True,
- verbose=False,
- visual=None,
- multiple=False,
给定一个正整数
n，factorint(n)返回一个字典，其中包含n的质因数作为键，它们的相应乘数作为值。例如：>>> from sympy.ntheory import factorint >>> factorint(2000) # 2000 = (2**4) * (5**3) {2: 4, 5: 3} >>> factorint(65537) # This number is prime {65537: 1}
对于小于2的输入，factorint 的行为如下：
factorint(1)返回空因式分解，{}factorint(0)返回{0:1}factorint(-n)将-1:1添加到因子中，然后对n进行因子分解。
部分因子分解：
如果指定了
limit(> 3)，则在执行试除法直到（并包括）限制（或进行相应数量的 rho/p-1 步）后停止搜索。如果有一个大数并且只对找到小因子（如果有的话）感兴趣，这很有用。请注意，设置限制并不妨碍早期找到更大的因子；它只是意味着最大的因子可能是合数。由于检查完全幂相对便宜，因此无论是否设置限制都会进行检查。例如，这个数字有两个小的因子和一个巨大的半素因子，这个半素因子不容易被分解：
>>> from sympy.ntheory import isprime >>> a = 1407633717262338957430697921446883 >>> f = factorint(a, limit=10000) >>> f == {991: 1, int(202916782076162456022877024859): 1, 7: 1} True >>> isprime(max(f)) False
这个数有一个小的因子，以及一个基数大于限制的剩余完全幂：
>>> factorint(3*101**7, limit=5) {3: 1, 101: 7}
因素列表：
如果
multiple设置为True，则返回一个包含质因数及其重数的列表。>>> factorint(24, multiple=True) [2, 2, 2, 3]
视觉分解：
如果
visual设置为True，那么它将返回整数的一个可视化因式分解。例如：>>> from sympy import pprint >>> pprint(factorint(4200, visual=True)) 3 1 2 1 2 *3 *5 *7
请注意，这是通过在 Mul 和 Pow 中使用 evaluate=False 标志实现的。如果你对一个表达式进行其他操作，其中 evaluate=False，它可能会求值。因此，你应该仅在可视化时使用 visual 选项，如果你想对因子执行操作，请使用 visual=False 返回的普通字典。
你可以通过将它们发送回 factorint 来轻松地在两种形式之间切换：
>>> from sympy import Mul >>> regular = factorint(1764); regular {2: 2, 3: 2, 7: 2} >>> pprint(factorint(regular)) 2 2 2 2 *3 *7
>>> visual = factorint(1764, visual=True); pprint(visual) 2 2 2 2 *3 *7 >>> print(factorint(visual)) {2: 2, 3: 2, 7: 2}
如果你想发送一个以部分分解形式表示的数字，你可以使用字典或未求值的表达式来实现：
>>> factorint(factorint({4: 2, 12: 3})) # twice to toggle to dict form {2: 10, 3: 3} >>> factorint(Mul(4, 12, evaluate=False)) {2: 4, 3: 1}
输出逻辑的表格如下：
toctree是一个 reStructuredText 指令 ，这是一个非常多功能的标记。指令可以有参数、选项和内容。真
假
其他
dict
mul
dict
mul
n
mul
dict
dict
mul
mul
dict
dict
注释
算法：
该函数在多种算法之间切换。试除法能快速找到小因子（数量级为1-5位），并在给定足够时间的情况下找到所有大因子。Pollard rho 和 p-1 算法用于提前找到大因子；它们通常能在几秒钟内找到数量级为10位的因子。
>>> factors = factorint(12345678910111213141516) >>> for base, exp in sorted(factors.items()): ... print('%s %s' % (base, exp)) ... 2 2 2507191691 1 1231026625769 1
这些方法中的任何一个都可以通过以下布尔参数选择性地禁用：
use_trial: 切换使用试除法use_rho: 切换使用 Pollard’s rho 方法use_pm1: 切换使用 Pollard 的 p-1 方法
factorint还会定期检查剩余部分是否为质数或完全幂，如果是，则停止。对于未计算的阶乘，它使用勒让德公式（定理）。
如果
verbose设置为True，将打印详细的进度。
- sympy.ntheory.factor_.factorrat(
- rat,
- limit=None,
- use_trial=True,
- use_rho=True,
- use_pm1=True,
- verbose=False,
- visual=None,
- multiple=False,
给定一个有理数
r，factorrat(r)返回一个字典，其中包含r的质因数作为键，它们的相应乘数作为值。例如：>>> from sympy import factorrat, S >>> factorrat(S(8)/9) # 8/9 = (2**3) * (3**-2) {2: 3, 3: -2} >>> factorrat(S(-1)/987) # -1/789 = -1 * (3**-1) * (7**-1) * (47**-1) {-1: 1, 3: -1, 7: -1, 47: -1}
请参阅
factorint的文档字符串，以获取以下关键字的详细解释和示例：limit: 整数限制，直到进行试验除法use_trial: 切换使用试除法use_rho: 切换使用 Pollard’s rho 方法use_pm1: 切换使用 Pollard 的 p-1 方法verbose: 切换进度详细打印multiple: 切换返回因子列表或字典visual: 切换输出产品的形式
- sympy.ntheory.factor_.primefactors(
- n,
- limit=None,
- verbose=False,
- **kwargs,
返回 n 的素因子排序列表，忽略重复项和任何因限制设置过低而未完全分解的复合因子。与 factorint() 不同，primefactors() 不会返回 -1 或 0。
- 参数:
- n整数
- 限制, 详细, **关键字参数
要传递给
factorint的额外关键字参数。由于kwargs是在版本 1.13 中新增的，为了兼容性，保留了limit和verbose。
- 返回:
- list(int) : 分解
n的质数列表质数列表除以
- list(int) : 分解
示例
>>> from sympy.ntheory import primefactors, factorint, isprime >>> primefactors(6) [2, 3] >>> primefactors(-5) [5]
>>> sorted(factorint(123456).items()) [(2, 6), (3, 1), (643, 1)] >>> primefactors(123456) [2, 3, 643]
>>> sorted(factorint(10000000001, limit=200).items()) [(101, 1), (99009901, 1)] >>> isprime(99009901) False >>> primefactors(10000000001, limit=300) [101]
- sympy.ntheory.factor_.divisors(n, generator=False, proper=False)[源代码][源代码]¶
返回 n 的所有因数，默认按 1..n 排序。如果 generator 是
True，则返回一个无序的生成器。如果 n 有很多质因数（包括重复的因数），n 的因数数量可能会非常大。如果只需要因数的数量，请使用 divisor_count(n)。
注释
这是Tim Peters在以下链接中引用的略有修改的版本：https://stackoverflow.com/questions/1010381/python-factorization
示例
>>> from sympy import divisors, divisor_count >>> divisors(24) [1, 2, 3, 4, 6, 8, 12, 24] >>> divisor_count(24) 8
>>> list(divisors(120, generator=True)) [1, 2, 4, 8, 3, 6, 12, 24, 5, 10, 20, 40, 15, 30, 60, 120]
- sympy.ntheory.factor_.proper_divisors(n, generator=False)[源代码][源代码]¶
返回 n 的所有除数，除了 n 本身，默认排序。如果 generator 是
True，则返回一个无序的生成器。示例
>>> from sympy import proper_divisors, proper_divisor_count >>> proper_divisors(24) [1, 2, 3, 4, 6, 8, 12] >>> proper_divisor_count(24) 7 >>> list(proper_divisors(120, generator=True)) [1, 2, 4, 8, 3, 6, 12, 24, 5, 10, 20, 40, 15, 30, 60]
- sympy.ntheory.factor_.divisor_count(n, modulus=1, proper=False)[源代码][源代码]¶
返回
n的约数个数。如果modulus不是 1，则只计算那些能被modulus整除的约数。如果proper为 True，则n的约数将不被计算在内。示例
>>> from sympy import divisor_count >>> divisor_count(6) 4 >>> divisor_count(6, 2) 2 >>> divisor_count(6, proper=True) 3
- sympy.ntheory.factor_.proper_divisor_count(n, modulus=1)[源代码][源代码]¶
返回
n的适当除数的数量。示例
>>> from sympy import proper_divisor_count >>> proper_divisor_count(6) 3 >>> proper_divisor_count(6, modulus=2) 1
- sympy.ntheory.factor_.udivisors(n, generator=False)[源代码][源代码]¶
返回 n 的所有单一因子，默认按 1..n 排序。如果 generator 为
True，则返回一个无序的生成器。如果 n 有很多质因数，n 的单位除数的数量可能会非常大。如果只需要单位除数的数量，请使用 udivisor_count(n)。
参考文献
示例
>>> from sympy.ntheory.factor_ import udivisors, udivisor_count >>> udivisors(15) [1, 3, 5, 15] >>> udivisor_count(15) 4
>>> sorted(udivisors(120, generator=True)) [1, 3, 5, 8, 15, 24, 40, 120]
- sympy.ntheory.factor_.udivisor_count(n)[源代码][源代码]¶
返回
n的单位除数的数量。- 参数:
- n整数
参考文献
示例
>>> from sympy.ntheory.factor_ import udivisor_count >>> udivisor_count(120) 8
- sympy.ntheory.factor_.antidivisors(n, generator=False)[源代码][源代码]¶
返回所有 n 的反除数，默认按 1..n 排序。
Antidivisors [1] 是那些不能以最大可能的余数来整除 n 的数。如果 generator 为 True，则返回一个无序的生成器。
参考文献
[1]示例
>>> from sympy.ntheory.factor_ import antidivisors >>> antidivisors(24) [7, 16]
>>> sorted(antidivisors(128, generator=True)) [3, 5, 15, 17, 51, 85]
- sympy.ntheory.factor_.antidivisor_count(n)[源代码][源代码]¶
返回
n的反除数 [1] 的数量。- 参数:
- n整数
参考文献
[1]示例
>>> from sympy.ntheory.factor_ import antidivisor_count >>> antidivisor_count(13) 4 >>> antidivisor_count(27) 5
- sympy.ntheory.factor_.totient(n)[源代码][源代码]¶
计算欧拉函数 phi(n)
自 1.13 版本弃用:
totient函数已被弃用。请改用sympy.functions.combinatorial.numbers.totient。更多信息请参阅其文档。详情请参阅 将符号函数从 ntheory 移动到 functions。totient(n)或 \(\phi(n)\) 是小于等于 n 且与 n 互质的正整数个数。- 参数:
- n整数
参考文献
示例
>>> from sympy.functions.combinatorial.numbers import totient >>> totient(1) 1 >>> totient(25) 20 >>> totient(45) == totient(5)*totient(9) True
- sympy.ntheory.factor_.reduced_totient(n)[源代码][源代码]¶
计算 Carmichael 约简完全数函数 lambda(n)
自 1.13 版本弃用:
reduced_totient函数已被弃用。请改用sympy.functions.combinatorial.numbers.reduced_totient。更多信息请参阅其文档。详情请参见 将符号函数从 ntheory 移动到 functions。reduced_totient(n)或 \(\lambda(n)\) 是使得 \(k^m \equiv 1 \mod n\) 对所有与 n 互质的 k 成立的最小 m > 0。参见
参考文献
[2]https://mathworld.wolfram.com/Carmichael函数.html
示例
>>> from sympy.functions.combinatorial.numbers import reduced_totient >>> reduced_totient(1) 1 >>> reduced_totient(8) 2 >>> reduced_totient(30) 4
- sympy.ntheory.factor_.divisor_sigma(n, k=1)[源代码][源代码]¶
计算正整数 n 的除数函数 \(\sigma_k(n)\)
自 1.13 版本弃用:
divisor_sigma函数已被弃用。请改用sympy.functions.combinatorial.numbers.divisor_sigma。更多信息请参阅其文档。详情请参见 将符号函数从 ntheory 移动到 functions。divisor_sigma(n, k)等于sum([x**k for x in divisors(n)])如果 n 的质因数分解为：
\[n = \prod_{i=1}^\omega p_i^{m_i},\]然后
\[\[\sigma_k(n) = \prod_{i=1}^\omega (1+p_i^k+p_i^{2k}+\cdots + p_i^{m_ik}).\]\]- 参数:
- n整数
- k整数，可选
和中的除数幂
对于 k = 0, 1:
divisor_sigma(n, 0)等于divisor_count(n)divisor_sigma(n, 1)等于sum(divisors(n))k 的默认值是 1。
参考文献
示例
>>> from sympy.functions.combinatorial.numbers import divisor_sigma >>> divisor_sigma(18, 0) 6 >>> divisor_sigma(39, 1) 56 >>> divisor_sigma(12, 2) 210 >>> divisor_sigma(37) 38
- sympy.ntheory.factor_.udivisor_sigma(n, k=1)[源代码][源代码]¶
计算正整数 n 的单位除数函数 \(\sigma_k^*(n)\)
自 1.13 版本弃用:
udivisor_sigma函数已被弃用。请改用sympy.functions.combinatorial.numbers.udivisor_sigma。更多信息请参阅其文档。详情请参阅 将符号函数从 ntheory 移动到 functions。udivisor_sigma(n, k)等于sum([x**k for x in udivisors(n)])如果 n 的质因数分解为：
\[n = \prod_{i=1}^\omega p_i^{m_i},\]然后
\[\sigma_k^*(n) = \prod_{i=1}^\omega (1+ p_i^{m_ik}).\]- 参数:
- k和中的除数幂
对于 k = 0, 1:
udivisor_sigma(n, 0)等于udivisor_count(n)udivisor_sigma(n, 1)等于sum(udivisors(n))k 的默认值是 1。
参考文献
示例
>>> from sympy.functions.combinatorial.numbers import udivisor_sigma >>> udivisor_sigma(18, 0) 4 >>> udivisor_sigma(74, 1) 114 >>> udivisor_sigma(36, 3) 47450 >>> udivisor_sigma(111) 152
- sympy.ntheory.factor_.core(n, t=2)[源代码][源代码]¶
计算正整数 n 的核(n, t) = \(core_t(n)\)
core_2(n)等于 n 的无平方部分如果 n 的质因数分解为：
\[n = \prod_{i=1}^\omega p_i^{m_i},\]然后
\[core_t(n) = \prod_{i=1}^\omega p_i^{m_i \mod t}.\]- 参数:
- n整数
- t整数
core(n, t) 计算 n 的 t 次幂自由部分
core(n, 2)是n的无平方部分core(n, 3)是n的无立方部分t 的默认值是 2。
参考文献
示例
>>> from sympy.ntheory.factor_ import core >>> core(24, 2) 6 >>> core(9424, 3) 1178 >>> core(379238) 379238 >>> core(15**11, 10) 15
- sympy.ntheory.factor_.digits(n, b=10, digits=None)[源代码][源代码]¶
返回
n在基数b中的数字列表。列表的第一个元素是b（如果n为负数，则为-b）。- 参数:
- n: 整数
返回其数字的数字。
- b: 整数
数字计算的基数。
- digits: 整数 (或 None 表示所有数字)
要返回的数字位数（必要时用零填充）。
参见
sympy.core.intfunc.num_digits,count_digits
示例
>>> from sympy.ntheory.digits import digits >>> digits(35) [10, 3, 5]
如果数字是负数，负号将被放置在基数上（这是返回列表中的第一个元素）：
>>> digits(-35) [-10, 3, 5]
可以选择10以外的基数（且大于1），通过
b来选择：>>> digits(27, b=2) [2, 1, 1, 0, 1, 1]
如果需要特定数量的数字，请使用
digits关键字：>>> digits(35, digits=4) [10, 0, 0, 3, 5]
计算正整数 n 的不同质因数的数量。
自 1.13 版本弃用:
primenu函数已被弃用。请改用sympy.functions.combinatorial.numbers.primenu。更多信息请参阅其文档。详情请参见 将符号函数从 ntheory 移动到 functions。如果 n 的质因数分解为：
\[n = \prod_{i=1}^k p_i^{m_i},\]那么
primenu(n)或 \(\nu(n)\) 是：\[\nu(n) = k.\]参见
参考文献
示例
>>> from sympy.functions.combinatorial.numbers import primenu >>> primenu(1) 0 >>> primenu(30) 3
- sympy.ntheory.factor_.primeomega(n)[源代码][源代码]¶
计算正整数 n 的质因数个数（包括重复计数）。
自 1.13 版本弃用:
primeomega函数已被弃用。请改用sympy.functions.combinatorial.numbers.primeomega。更多信息请参阅其文档。详情请参见 将符号函数从 ntheory 移动到 functions。如果 n 的质因数分解为：
\[n = \prod_{i=1}^k p_i^{m_i},\]那么
primeomega(n)或 \(\Omega(n)\) 是：\[\Omega(n) = \sum_{i=1}^k m_i.\]参见
参考文献
示例
>>> from sympy.functions.combinatorial.numbers import primeomega >>> primeomega(1) 0 >>> primeomega(20) 3
- sympy.ntheory.factor_.mersenne_prime_exponent(nth)[源代码][源代码]¶
返回第 n 个梅森素数的指数
i（其形式为 \(2^i - 1\)）。示例
>>> from sympy.ntheory.factor_ import mersenne_prime_exponent >>> mersenne_prime_exponent(1) 2 >>> mersenne_prime_exponent(20) 4423
- sympy.ntheory.factor_.is_perfect(n)[源代码][源代码]¶
如果
n是完美数，则返回 True，否则返回 False。一个完美数等于其所有正的、适当的因子的和。
参考文献
示例
>>> from sympy.functions.combinatorial.numbers import divisor_sigma >>> from sympy.ntheory.factor_ import is_perfect, divisors >>> is_perfect(20) False >>> is_perfect(6) True >>> 6 == divisor_sigma(6) - 6 == sum(divisors(6)[:-1]) True
- sympy.ntheory.factor_.abundance(n)[源代码][源代码]¶
返回一个数的正因数之和与该数本身的差值。
示例
>>> from sympy.ntheory import abundance, is_perfect, is_abundant >>> abundance(6) 0 >>> is_perfect(6) True >>> abundance(10) -2 >>> is_abundant(10) False
- sympy.ntheory.factor_.is_abundant(n)[源代码][源代码]¶
如果
n是盈数，则返回 True，否则返回 False。一个丰数小于其所有正的真因数之和。
参考文献
示例
>>> from sympy.ntheory.factor_ import is_abundant >>> is_abundant(20) True >>> is_abundant(15) False
- sympy.ntheory.factor_.is_deficient(n)[源代码][源代码]¶
如果
n是亏数，则返回 True，否则返回 False。一个不足数大于其所有正的真因数之和。
参考文献
示例
>>> from sympy.ntheory.factor_ import is_deficient >>> is_deficient(20) False >>> is_deficient(15) True
- sympy.ntheory.factor_.is_amicable(m, n)[源代码][源代码]¶
如果数字 \(m\) 和 \(n\) 是“亲和的”，则返回 True，否则返回 False。
亲和数是两个不同的数，它们的关系是每个数的真因数之和等于另一个数。
参考文献
[1]示例
>>> from sympy.functions.combinatorial.numbers import divisor_sigma >>> from sympy.ntheory.factor_ import is_amicable >>> is_amicable(220, 284) True >>> divisor_sigma(220) == divisor_sigma(284) True
- sympy.ntheory.factor_.is_carmichael(n)[源代码][源代码]¶
如果数字 \(n\) 是卡迈克尔数，则返回 True，否则返回 False。
- 参数:
- n整数
参考文献
[1]
- sympy.ntheory.modular.symmetric_residue(a, m)[源代码][源代码]¶
返回余数模 m，使其在模的一半以内。
>>> from sympy.ntheory.modular import symmetric_residue >>> symmetric_residue(1, 6) 1 >>> symmetric_residue(4, 6) -2
- sympy.ntheory.modular.crt(m, v, symmetric=False, check=True)[源代码][源代码]¶
中国剩余定理。
假设m中的模数是两两互质的。输出是一个整数f，使得对于v和m中的每一对，都有f = v_i mod m_i。如果``symmetric``为False，则返回一个正整数，否则|f|将小于或等于模数的LCM，因此f可能为负数。
如果模数不是互质的，当结果的测试被发现是错误的时，将返回正确的结果。如果没有解决方案，结果将为 None。
如果已知模数是互质的，可以将关键字
check设置为 False。参见
solve_congruencesympy.polys.galoistools.gf_crt此例程使用的低级crt例程
示例
作为一个例子，考虑一组余数
U = [49, 76, 65]和一组模数M = [99, 97, 95]。那么我们有:>>> from sympy.ntheory.modular import crt >>> crt([99, 97, 95], [49, 76, 65]) (639985, 912285)
这是正确结果，因为:
>>> [639985 % m for m in [99, 97, 95]] [49, 76, 65]
如果模数不是互质的，如果你使用
check=False，你可能会得到一个错误的结果：>>> crt([12, 6, 17], [3, 4, 2], check=False) (954, 1224) >>> [954 % m for m in [12, 6, 17]] [6, 0, 2] >>> crt([12, 6, 17], [3, 4, 2]) is None True >>> crt([3, 6], [2, 5]) (5, 6)
注意：gf_crt 的参数顺序相对于 crt 是颠倒的，并且 solve_congruence 接受余数、模数对。
程序员注释：与其检查所有模数的对是否没有共享的GCD（一个O(n**2)的测试），也与其分解所有模数并查看是否有共同的因子，不如执行一个检查结果是否给出指示的余数的操作——这是一个O(n)的操作。
- sympy.ntheory.modular.crt1(m)[源代码][源代码]¶
中国剩余定理的第一部分，适用于多次应用。
参见
示例
>>> from sympy.ntheory.modular import crt, crt1, crt2 >>> m = [99, 97, 95] >>> v = [49, 76, 65]
以下两个代码具有相同的结果。
>>> crt(m, v) (639985, 912285)
>>> mm, e, s = crt1(m) >>> crt2(m, v, mm, e, s) (639985, 912285)
然而，当我们想要固定
m并计算多个v时，速度会更快，即以下情况：>>> mm, e, s = crt1(m) >>> vs = [[52, 21, 37], [19, 46, 76]] >>> for v in vs: ... print(crt2(m, v, mm, e, s)) (397042, 912285) (803206, 912285)
- sympy.ntheory.modular.crt2(m, v, mm, e, s, symmetric=False)[源代码][源代码]¶
中国剩余定理的第二部分，适用于多次应用。
参见
crt1以了解用法。参见
示例
>>> from sympy.ntheory.modular import crt1, crt2 >>> mm, e, s = crt1([18, 42, 6]) >>> crt2([18, 42, 6], [0, 0, 0], mm, e, s) (0, 4536)
- sympy.ntheory.modular.solve_congruence(*remainder_modulus_pairs, **hint)[源代码][源代码]¶
计算整数
n，当它被mi除时余数为ai，其中ai和mi作为对提供给此函数：((a1, m1), (a2, m2), …)。如果没有解，则返回 None。否则返回n及其模数。mi的值不必是互质的。如果已知模数不是互质的，则可以将提示check设置为 False（默认=True），并且将跳过通过 crt() 进行更快解决方案的检查（当模数互质时有效）。如果提示
symmetric为 True（默认是 False），n的值将在模数的 1/2 范围内，可能是负数。参见
crt实现中国剩余定理的高级例程
示例
>>> from sympy.ntheory.modular import solve_congruence
2 mod 3、3 mod 5 和 2 mod 7 的数字是多少？
>>> solve_congruence((2, 3), (3, 5), (2, 7)) (23, 105) >>> [23 % m for m in [3, 5, 7]] [2, 3, 2]
如果你更喜欢将所有余数放在一个列表中，将所有模数放在另一个列表中，请这样发送参数：
>>> solve_congruence(*zip((2, 3, 2), (3, 5, 7))) (23, 105)
模数不必互质；在这种情况下，可能有也可能没有解：
>>> solve_congruence((2, 3), (4, 6)) is None True
>>> solve_congruence((2, 3), (5, 6)) (5, 6)
对称标志将使结果在模数的1/2以内：
>>> solve_congruence((2, 3), (5, 6), symmetric=True) (-1, 6)
- sympy.ntheory.multinomial.binomial_coefficients(n)[源代码][源代码]¶
返回一个包含对 \({(k1,k2) : C_kn}\) 的字典，其中 \(C_kn\) 是二项式系数，且 \(n=k1+k2\)。
示例
>>> from sympy.ntheory import binomial_coefficients >>> binomial_coefficients(9) {(0, 9): 1, (1, 8): 9, (2, 7): 36, (3, 6): 84, (4, 5): 126, (5, 4): 126, (6, 3): 84, (7, 2): 36, (8, 1): 9, (9, 0): 1}
- sympy.ntheory.multinomial.binomial_coefficients_list(n)[源代码][源代码]¶
返回一个二项式系数的列表，作为帕斯卡三角形的行。
示例
>>> from sympy.ntheory import binomial_coefficients_list >>> binomial_coefficients_list(9) [1, 9, 36, 84, 126, 126, 84, 36, 9, 1]
- sympy.ntheory.multinomial.multinomial_coefficients(m, n)[源代码][源代码]¶
返回一个包含对
{(k1,k2,..,km) : C_kn}的字典，其中C_kn是多项式系数，使得n=k1+k2+..+km。注释
该算法基于以下结果：
\[\binom{n}{k_1, \ldots, k_m} = \frac{k_1 + 1}{n - k_1} \sum_{i=2}^m \binom{n}{k_1 + 1, \ldots, k_i - 1, \ldots}\]由 Yann Laigle-Chapuy 贡献给 Sage 的代码，经作者许可复制。
示例
>>> from sympy.ntheory import multinomial_coefficients >>> multinomial_coefficients(2, 5) # indirect doctest {(0, 5): 1, (1, 4): 5, (2, 3): 10, (3, 2): 10, (4, 1): 5, (5, 0): 1}
- sympy.ntheory.multinomial.multinomial_coefficients_iterator(
- m,
- n,
- _tuple=<class 'tuple'>,
多项式系数迭代器
此例程已针对 \(m\) 相对于 \(n\) 较大时进行了优化，利用了以下事实：当单项式元组 \(t\) 去除零后，其系数与
multinomial_coefficients(n, n)中的单项式元组的系数相同。因此，后者的系数被预先计算以节省内存和时间。>>> from sympy.ntheory.multinomial import multinomial_coefficients >>> m53, m33 = multinomial_coefficients(5,3), multinomial_coefficients(3,3) >>> m53[(0,0,0,1,2)] == m53[(0,0,1,0,2)] == m53[(1,0,2,0,0)] == m33[(0,1,2)] True
示例
>>> from sympy.ntheory.multinomial import multinomial_coefficients_iterator >>> it = multinomial_coefficients_iterator(20,3) >>> next(it) ((3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0), 1)
- sympy.ntheory.partitions_.npartitions(n, verbose=False)[源代码][源代码]¶
计算分区函数 P(n)，即 n 可以写成正整数之和的方式数。
自 1.13 版本弃用:
npartitions函数已被弃用。请改用sympy.functions.combinatorial.numbers.partition。更多信息请参阅其文档。详情请参见 将符号函数从 ntheory 移动到 functions。P(n) 是使用 Hardy-Ramanujan-Rademacher 公式 [1] 计算的。
此实现的正确性已通过 \(10^{10}\) 进行了测试。
参考文献
示例
>>> from sympy.functions.combinatorial.numbers import partition >>> partition(25) 1958
- sympy.ntheory.primetest.is_fermat_pseudoprime(n, a)[源代码][源代码]¶
如果
n是素数或是一个与a互质且满足模算术同余关系的奇合数，则返回 True：\[a^{n-1} \equiv 1 \pmod{n}\]（其中 mod 指的是取模运算）。
- 参数:
- n整数
n是一个正整数。- a整数
a是一个正整数。a和n应该互质。
- 返回:
- bool : 如果
n是质数，它总是返回True。如果 返回
True的合数被称为费马伪素数。
- bool : 如果
参考文献
示例
>>> from sympy.ntheory.primetest import is_fermat_pseudoprime >>> from sympy.ntheory.factor_ import isprime >>> for n in range(1, 1000): ... if is_fermat_pseudoprime(n, 2) and not isprime(n): ... print(n) 341 561 645
- sympy.ntheory.primetest.is_euler_pseudoprime(n, a)[源代码][源代码]¶
如果
n是素数或是一个与a互质且满足模算术同余关系的奇合数，则返回 True：\[a^{(n-1)/2} \equiv \pm 1 \pmod{n}\]（其中 mod 指的是取模运算）。
- 参数:
- n整数
n是一个正整数。- a整数
a是一个正整数。a和n应该互质。
- 返回:
- bool : 如果
n是质数，它总是返回True。如果 返回
True的合数被称为欧拉伪素数。
- bool : 如果
参考文献
[1]https://en.wikipedia.org/wiki/Euler_伪素数
示例
>>> from sympy.ntheory.primetest import is_euler_pseudoprime >>> from sympy.ntheory.factor_ import isprime >>> for n in range(1, 1000): ... if is_euler_pseudoprime(n, 2) and not isprime(n): ... print(n) 341 561
- sympy.ntheory.primetest.is_euler_jacobi_pseudoprime(n, a)[源代码][源代码]¶
如果
n是素数或是一个与a互质且满足模算术同余关系的奇合数，则返回 True：\[a^{(n-1)/2} \equiv \left(\frac{a}{n}\right) \pmod{n}\]（其中 mod 指的是取模运算）。
- 参数:
- n整数
n是一个正整数。- a整数
a是一个正整数。a和n应该互质。
- 返回:
- bool : 如果
n是质数，它总是返回True。如果 返回
True的合数被称为欧拉-雅可比伪素数。
- bool : 如果
参考文献
[1]https://en.wikipedia.org/wiki/Euler%E2%80%93Jacobi_伪素数
示例
>>> from sympy.ntheory.primetest import is_euler_jacobi_pseudoprime >>> from sympy.ntheory.factor_ import isprime >>> for n in range(1, 1000): ... if is_euler_jacobi_pseudoprime(n, 2) and not isprime(n): ... print(n) 561
- sympy.ntheory.primetest.is_square(n, prep=True)[源代码][源代码]¶
如果对于某个整数 a，n == a * a 成立，则返回 True，否则返回 False。如果怀疑 n 不 是平方数，那么这是一个快速确认它不是平方数的方法。
参考文献
示例
>>> from sympy.ntheory.primetest import is_square >>> is_square(25) True >>> is_square(2) False
- sympy.ntheory.primetest.mr(n, bases)[源代码][源代码]¶
对 n 执行 Miller-Rabin 强伪素数测试，使用给定的基底/见证列表。
参考文献
[1]Richard Crandall & Carl Pomerance (2005), “素数：计算视角”, Springer, 第二版, 135-138
阈值列表及其所需的基础如下：https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test#Deterministic_variants
示例
>>> from sympy.ntheory.primetest import mr >>> mr(1373651, [2, 3]) False >>> mr(479001599, [31, 73]) True
- sympy.ntheory.primetest.is_lucas_prp(n)[源代码][源代码]¶
使用Selfridge参数的标准Lucas合性测试。如果n肯定是合数，则返回False；如果n是Lucas可能素数，则返回True。
这通常与 Miller-Rabin 测试结合使用。
参考文献
[1]Robert Baillie, Samuel S. Wagstaff, Lucas Pseudoprimes, Math. Comp. Vol 35, Number 152 (1980), pp. 1391-1417, https://doi.org/10.1090%2FS0025-5718-1980-0583518-6 http://mpqs.free.fr/LucasPseudoprimes.pdf
[2]OEIS A217120: Lucas 伪素数 https://oeis.org/A217120
示例
>>> from sympy.ntheory.primetest import isprime, is_lucas_prp >>> for i in range(10000): ... if is_lucas_prp(i) and not isprime(i): ... print(i) 323 377 1159 1829 3827 5459 5777 9071 9179
- sympy.ntheory.primetest.is_strong_lucas_prp(n)[源代码][源代码]¶
使用Selfridge参数的强Lucas复合性测试。如果n肯定是合数，则返回False；如果n是强Lucas可能素数，则返回True。
这通常与 Miller-Rabin 测试结合使用，特别是当与 M-R 基 2 结合时，会创建强 BPSW 测试。
参考文献
[1]Robert Baillie, Samuel S. Wagstaff, Lucas Pseudoprimes, Math. Comp. Vol 35, Number 152 (1980), pp. 1391-1417, https://doi.org/10.1090%2FS0025-5718-1980-0583518-6 http://mpqs.free.fr/LucasPseudoprimes.pdf
[2]OEIS A217255: 强Lucas伪素数 https://oeis.org/A217255
[4]示例
>>> from sympy.ntheory.primetest import isprime, is_strong_lucas_prp >>> for i in range(20000): ... if is_strong_lucas_prp(i) and not isprime(i): ... print(i) 5459 5777 10877 16109 18971
- sympy.ntheory.primetest.is_extra_strong_lucas_prp(n)[源代码][源代码]¶
额外强 Lucas 合数测试。如果 n 肯定是合数，则返回 False；如果 n 是“额外强”的 Lucas 可能素数，则返回 True。
使用 P = 3, Q = 1 选择参数，然后递增 P 直到 (D|n) == -1。测试本身如 [1] 中所定义，来自 Mo 和 Jones 的预印本。参数选择和测试与 OEIS A217719、Perl 的 Math::Prime::Util 以及 Wikipedia 上的 Lucas 伪素数页面中使用的方法相同。
它比强测试快20-50%。
由于选择了不同的参数，强Lucas伪素数和额外强Lucas伪素数之间没有关系。特别是，一个不是另一个的子集。
参考文献
[1]Jon Grantham, Frobenius 伪素数, Math. Comp. 第70卷, 第234期 (2001), 第873-891页, https://doi.org/10.1090%2FS0025-5718-00-01197-2
[2]OEIS A217719: 超强Lucas伪素数 https://oeis.org/A217719
示例
>>> from sympy.ntheory.primetest import isprime, is_extra_strong_lucas_prp >>> for i in range(20000): ... if is_extra_strong_lucas_prp(i) and not isprime(i): ... print(i) 989 3239 5777 10877
- sympy.ntheory.primetest.proth_test(n)[源代码][源代码]¶
测试 Proth 数 \(n = k2^m + 1\) 是否为素数。其中 k 是一个正奇数，且 \(2^m > k\)。
- 参数:
- n整数
n是一个 Proth 数
- 返回:
- bool : 如果
True，那么n是 Proth 素数如果
- bool : 如果
- Raises:
- ValueError
如果
n不是 Proth 数。
参考文献
示例
>>> from sympy.ntheory.primetest import proth_test >>> proth_test(41) True >>> proth_test(57) False
- sympy.ntheory.primetest.is_mersenne_prime(n)[源代码][源代码]¶
如果
n是梅森素数，则返回 True，否则返回 False。梅森素数是一个具有形式 \(2^i - 1\) 的素数。
参考文献
示例
>>> from sympy.ntheory.factor_ import is_mersenne_prime >>> is_mersenne_prime(6) False >>> is_mersenne_prime(127) True
- sympy.ntheory.primetest.isprime(n)[源代码][源代码]¶
测试 n 是否为质数（True）或不是（False）。对于 n < 2^64，答案是确定的；更大的 n 值有很小的概率实际上是伪质数。
负数（例如 -2）不被视为质数。
第一步是寻找平凡因子，如果找到则可以快速返回。接下来，如果筛子足够大，则在筛子上使用二分搜索。对于小数，执行一组确定的 Miller-Rabin 测试，其基底在其范围内已知没有反例。最后，如果数字大于 2^64，则执行强 BPSW 测试。虽然这是一个概率素性测试，并且我们相信存在反例，但目前没有已知的反例。
参见
sympy.ntheory.generate.primerange生成给定范围内的所有素数
sympy.functions.combinatorial.numbers.primepi返回小于或等于 n 的素数个数
sympy.ntheory.generate.prime返回第 n 个质数
注释
此例程仅适用于整数输入，不适用于可能表示数字的数值表达式。浮点数也被拒绝作为输入，因为它们表示有限精度的数字。虽然允许 7.0 表示整数很诱人，但如果允许这样做，可能会出现“静默通过”的错误：
>>> from sympy import Float, S >>> int(1e3) == 1e3 == 10**3 True >>> int(1e23) == 1e23 True >>> int(1e23) == 10**23 False
>>> near_int = 1 + S(1)/10**19 >>> near_int == int(near_int) False >>> n = Float(near_int, 10) # truncated by precision >>> n % 1 == 0 True >>> n = Float(near_int, 20) >>> n % 1 == 0 False
参考文献
[1][2]Robert Baillie, Samuel S. Wagstaff, Lucas Pseudoprimes, Math. Comp. Vol 35, Number 152 (1980), pp. 1391-1417, https://doi.org/10.1090%2FS0025-5718-1980-0583518-6 http://mpqs.free.fr/LucasPseudoprimes.pdf
[3]示例
>>> from sympy.ntheory import isprime >>> isprime(13) True >>> isprime(15) False
- sympy.ntheory.residue_ntheory.n_order(a, n)[源代码][源代码]¶
返回
a对n的模的顺序。- 参数:
- a整数
- n整数, n > 1。a 和 n 应互质。
- 返回:
- int :
a模n的阶顺序
- int :
- Raises:
- ValueError
如果 \(n \le 1\) 或 \(\gcd(a, n) \neq 1\)。如果
a或n不是整数。
参见
is_primitive_root我们称
a是n的原根，当a模n的阶等于totient(n)。
示例
>>> from sympy.ntheory import n_order >>> n_order(3, 7) 6 >>> n_order(4, 7) 3
- sympy.ntheory.residue_ntheory.is_primitive_root(a, p)[源代码][源代码]¶
如果
a是p的一个原根，则返回 True。- 参数:
- a整数
- p : 整数,
p> 1.a和p应互质整数
- 返回:
- bool : 如果为 True，则
a是p的原根。如果为真，
- bool : 如果为 True，则
- Raises:
- ValueError
如果 \(p \le 1\) 或 \(\gcd(a, p) \neq 1\)。如果
a或p不是整数。
示例
>>> from sympy.functions.combinatorial.numbers import totient >>> from sympy.ntheory import is_primitive_root, n_order >>> is_primitive_root(3, 10) True >>> is_primitive_root(9, 10) False >>> n_order(3, 10) == totient(10) True >>> n_order(9, 10) == totient(10) False
- sympy.ntheory.residue_ntheory.primitive_root(p, smallest=True)[源代码][源代码]¶
返回
p的一个原根，或者返回 None。- 参数:
- p整数, p > 1
- 最小如果为真，则返回最小的原根，否则返回 None
- 返回:
- int | None
如果存在原根，则返回
p的原根。如果不存在，则返回 None。
- Raises:
- ValueError
如果 \(p \le 1\) 或
p不是整数。
参考文献
[1]Stein 的 “初等数论” (2011), 第44页
[2]Hackman 的《初等数论》（2009年），第C章
示例
>>> from sympy.ntheory.residue_ntheory import primitive_root >>> primitive_root(19) 2 >>> primitive_root(21) is None True >>> primitive_root(50, smallest=False) 27
- sympy.ntheory.residue_ntheory.sqrt_mod(a, p, all_roots=False)[源代码][源代码]¶
找到
x**2 = a mod p的根。- 参数:
- a整数
- p正整数
- all_roots如果为真，则返回根列表，否则返回 None
注释
如果没有根，则返回 None；否则返回的根小于或等于
p // 2；通常不是最小的根。只有在它是唯一根的情况下，才返回p // 2。仅在预期所有根都能放入内存时使用
all_roots；否则使用sqrt_mod_iter。示例
>>> from sympy.ntheory import sqrt_mod >>> sqrt_mod(11, 43) 21 >>> sqrt_mod(17, 32, True) [7, 9, 23, 25]
- sympy.ntheory.residue_ntheory.sqrt_mod_iter(a, p, domain=<class 'int'>)[源代码][源代码]¶
迭代
x**2 = a mod p的解。- 参数:
- a整数
- p正整数
- domain : 整数域,
int,ZZ或Integer整数域,
参见
sqrt_mod相同的功能，但您希望得到一个排序列表或仅一个解决方案。
示例
>>> from sympy.ntheory.residue_ntheory import sqrt_mod_iter >>> list(sqrt_mod_iter(11, 43)) [21, 22]
- sympy.ntheory.residue_ntheory.quadratic_residues(p) list[int][源代码][源代码]¶
返回二次剩余的列表。
示例
>>> from sympy.ntheory.residue_ntheory import quadratic_residues >>> quadratic_residues(7) [0, 1, 2, 4]
- sympy.ntheory.residue_ntheory.nthroot_mod(a, n, p, all_roots=False)[源代码][源代码]¶
找到
x**n = a mod p的解。- 参数:
- a整数
- n正整数
- p正整数
- all_roots如果为 False 则返回最小的根，否则返回根的列表
- 返回:
- list[int] | int | None
x**n = a mod p的解。输出类型的表格如下：所有根目录
有根源
返回
真
是
list[int]
真
不
[]
假
是
整数
假
不
无
- Raises:
- ValueError
如果
a、n或p不是整数。如果n或p不是正数。
参考文献
[1]Hackman 的 “Elementary Number Theory” (2009), 第76页
示例
>>> from sympy.ntheory.residue_ntheory import nthroot_mod >>> nthroot_mod(11, 4, 19) 8 >>> nthroot_mod(11, 4, 19, True) [8, 11] >>> nthroot_mod(68, 3, 109) 23
- sympy.ntheory.residue_ntheory.is_nthpow_residue(a, n, m)[源代码][源代码]¶
如果
x**n == a (mod m)有解，则返回 True。参考文献
[1]Hackman 的 “Elementary Number Theory” (2009), 第76页
- sympy.ntheory.residue_ntheory.is_quad_residue(a, p)[源代码][源代码]¶
如果
a(modp) 在平方数模p的集合中，即 a % p 在集合([i**2 % p for i in range(p)])中，则返回 True。- 参数:
- a整数
- p正整数
- 返回:
- bool : 如果为 True，则
x**2 == a (mod p)有解。如果为真，
- bool : 如果为 True，则
- Raises:
- ValueError
如果
a，p不是整数。如果p不是正数。
示例
>>> from sympy.ntheory import is_quad_residue >>> is_quad_residue(21, 100) True
确实，
pow(39, 2, 100)的结果是 21。>>> is_quad_residue(21, 120) False
也就是说，对于任何整数
x，pow(x, 2, 120)不等于 21。如果
p是一个奇素数，将使用迭代方法来进行判断：>>> from sympy.ntheory import is_quad_residue >>> sorted(set([i**2 % 7 for i in range(7)])) [0, 1, 2, 4] >>> [j for j in range(7) if is_quad_residue(j, 7)] [0, 1, 2, 4]
- sympy.ntheory.residue_ntheory.legendre_symbol(a, p)[源代码][源代码]¶
返回勒让德符号 \((a / p)\)。
自 1.13 版本弃用:
legendre_symbol函数已被弃用。请改用sympy.functions.combinatorial.numbers.legendre_symbol。更多信息请参阅其文档。详情请参见 将符号函数从 ntheory 移动到 functions。对于整数
a和奇素数p，勒让德符号定义为\[\begin{split}\genfrac(){}{}{a}{p} = \begin{cases} 0 & \text{如果 } p \text{ 整除 } a\\ 1 & \text{如果 } a \text{ 是模 } p \text{ 的二次剩余}\\ -1 & \text{如果 } a \text{ 是模 } p \text{ 的二次非剩余} \end{cases}\end{split}\]- 参数:
- a整数
- p奇素数
示例
>>> from sympy.functions.combinatorial.numbers import legendre_symbol >>> [legendre_symbol(i, 7) for i in range(7)] [0, 1, 1, -1, 1, -1, -1] >>> sorted(set([i**2 % 7 for i in range(7)])) [0, 1, 2, 4]
- sympy.ntheory.residue_ntheory.jacobi_symbol(m, n)[源代码][源代码]¶
返回雅可比符号 \((m / n)\)。
自 1.13 版本弃用:
jacobi_symbol函数已被弃用。请改用sympy.functions.combinatorial.numbers.jacobi_symbol。更多信息请参阅其文档。详情请参见 将符号函数从 ntheory 移动到 functions。对于任意整数
m和任意正奇整数n，雅可比符号定义为对应于n的质因数的勒让德符号的乘积：\[\genfrac(){}{}{m}{n} = \genfrac(){}{}{m}{p^{1}}^{\alpha_1} \genfrac(){}{}{m}{p^{2}}^{\alpha_2} ... \genfrac(){}{}{m}{p^{k}}^{\alpha_k} \text{ 其中 } n = p_1^{\alpha_1} p_2^{\alpha_2} ... p_k^{\alpha_k}\]类似于勒让德符号，如果雅可比符号 \(\genfrac(){}{}{m}{n} = -1\)，那么
m是模n的二次非剩余。但是，与勒让德符号不同，如果雅可比符号 \(\genfrac(){}{}{m}{n} = 1\)，那么
m可能是也可能不是n的模二次剩余。- 参数:
- m整数
- n奇正整数
示例
>>> from sympy.functions.combinatorial.numbers import jacobi_symbol, legendre_symbol >>> from sympy import S >>> jacobi_symbol(45, 77) -1 >>> jacobi_symbol(60, 121) 1
jacobi_symbol和legendre_symbol之间的关系可以如下所示：>>> L = legendre_symbol >>> S(45).factors() {3: 2, 5: 1} >>> jacobi_symbol(7, 45) == L(7, 3)**2 * L(7, 5)**1 True
- sympy.ntheory.residue_ntheory.mobius(n)[源代码][源代码]¶
Mobius 函数将自然数映射到 {-1, 0, 1}
自 1.13 版本弃用:
mobius函数已被弃用。请改用sympy.functions.combinatorial.numbers.mobius。更多信息请参阅其文档。详情请参见 将符号函数从 ntheory 移动到 functions。- 它定义如下：
\(1\) 如果 \(n = 1\)。
\(0\) 如果 \(n\) 有平方的质因数。
\((-1)^k\) 如果 \(n\) 是一个无平方因子的正整数，且有 \(k\) 个质因数。
它是数论和组合数学中的一个重要乘法函数。它在数学级数、代数数论中都有应用，并且在物理学中也有应用（费米子算符在Möbius函数模型中有非常具体的实现）。
- 参数:
- n正整数
参考文献
[1][2]Thomas Koshy 的《Elementary Number Theory with Applications》
示例
>>> from sympy.functions.combinatorial.numbers import mobius >>> mobius(13*7) 1 >>> mobius(1) 1 >>> mobius(13*7*5) -1 >>> mobius(13**2) 0
- sympy.ntheory.residue_ntheory.discrete_log(
- n,
- a,
- b,
- order=None,
- prime_order=None,
计算
a对模n的b的离散对数。这是一个递归函数，用于将复合阶循环群中的离散对数问题简化为素数阶循环群中的问题。
它根据问题的不同（子群阶的大小、是否为素数）采用不同的算法：
试乘法
小步大步法
Pollard’s Rho
索引演算法
Pohlig-Hellman
参考文献
[2]《应用密码学手册》，Menezes, A. J., Van, O. P. C., & Vanstone, S. A. (1997)。
示例
>>> from sympy.ntheory import discrete_log >>> discrete_log(41, 15, 7) 3
- sympy.ntheory.residue_ntheory.quadratic_congruence(a, b, c, n)[源代码][源代码]¶
求解 \(a x^2 + b x + c \equiv 0 \pmod{n}\) 的解。
- 参数:
- a整数
- b整数
- c整数
- n整数
一个正整数。
- 返回:
- list[int]
解决方案的排序列表。如果不存在解决方案，则为
[]。
参见
polynomial_congruence求解多项式同余
示例
>>> from sympy.ntheory.residue_ntheory import quadratic_congruence >>> quadratic_congruence(2, 5, 3, 7) # 2x^2 + 5x + 3 = 0 (mod 7) [2, 6] >>> quadratic_congruence(8, 6, 4, 15) # No solution []
- sympy.ntheory.residue_ntheory.polynomial_congruence(expr, m)[源代码][源代码]¶
找到多项式同余方程模 m 的解。
- 参数:
- 表达式整系数多项式
- m正整数
参见
sympy.polys.galoistools.gf_csolve此例程使用的低级求解例程
示例
>>> from sympy.ntheory import polynomial_congruence >>> from sympy.abc import x >>> expr = x**6 - 2*x**5 -35 >>> polynomial_congruence(expr, 6125) [3257]
- sympy.ntheory.residue_ntheory.binomial_mod(n, m, k)[源代码][源代码]¶
计算
binomial(n, m) % k。- 参数:
- n一个整数
- m一个整数
- k一个正整数
参考文献
[1]模素数幂的二项式系数，Andrew Granville，可用链接: https://web.archive.org/web/20170202003812/http://www.dms.umontreal.ca/~andrew/PDF/BinCoeff.pdf
示例
>>> from sympy.ntheory.residue_ntheory import binomial_mod >>> binomial_mod(10, 2, 6) # binomial(10, 2) = 45 3 >>> binomial_mod(17, 9, 10) # binomial(17, 9) = 24310 0
- sympy.ntheory.continued_fraction.continued_fraction(a) list[源代码][源代码]¶
返回一个有理数或二次无理数的连分数表示。
示例
>>> from sympy.ntheory.continued_fraction import continued_fraction >>> from sympy import sqrt >>> continued_fraction((1 + 2*sqrt(3))/5) [0, 1, [8, 3, 34, 3]]
- sympy.ntheory.continued_fraction.continued_fraction_convergents(cf)[源代码][源代码]¶
返回一个迭代器，遍历连分数（cf）的渐近分数。
参数应为以下两种形式之一：- 一个部分商的列表，最后一个元素可能是一个重复的部分商列表，例如可能由 continued_fraction 和 continued_fraction_periodic 返回。- 一个返回连续部分商的可迭代对象，例如可能由 continued_fraction_iterator 返回。
在计算连分数的渐近分数时，连分数不需要严格处于规范形式（所有整数，除第一个外均为正数）。扩展中可能存在有理数和负数元素。
示例
>>> from sympy.core import pi >>> from sympy import S >>> from sympy.ntheory.continued_fraction import continued_fraction_convergents, continued_fraction_iterator
>>> list(continued_fraction_convergents([0, 2, 1, 2])) [0, 1/2, 1/3, 3/8]
>>> list(continued_fraction_convergents([1, S('1/2'), -7, S('1/4')])) [1, 3, 19/5, 7]
>>> it = continued_fraction_convergents(continued_fraction_iterator(pi)) >>> for n in range(7): ... print(next(it)) 3 22/7 333/106 355/113 103993/33102 104348/33215 208341/66317
>>> it = continued_fraction_convergents([1, [1, 2]]) # sqrt(3) >>> for n in range(7): ... print(next(it)) 1 2 5/3 7/4 19/11 26/15 71/41
- sympy.ntheory.continued_fraction.continued_fraction_iterator(x)[源代码][源代码]¶
返回 x 的连分数展开作为迭代器。
参考文献
[1]示例
>>> from sympy import Rational, pi >>> from sympy.ntheory.continued_fraction import continued_fraction_iterator
>>> list(continued_fraction_iterator(Rational(3, 8))) [0, 2, 1, 2] >>> list(continued_fraction_iterator(Rational(-3, 8))) [-1, 1, 1, 1, 2]
>>> for i, v in enumerate(continued_fraction_iterator(pi)): ... if i > 7: ... break ... print(v) 3 7 15 1 292 1 1 1
- sympy.ntheory.continued_fraction.continued_fraction_periodic(
- p,
- q,
- d=0,
- s=1,
找到二次无理数的周期连分数展开。
计算一个有理数或二次无理数的连分数展开，即 \(\frac{p + s\sqrt{d}}{q}\)，其中 \(p\)、\(q \ne 0\) 和 \(d \ge 0\) 是整数。
返回连分数表示（标准形式）作为整数列表，可选地（对于二次无理数）以表示重复数字的整数列表结束。
- 参数:
- p整数
数字分子的有理部分
- q整数
数字的分母
- dint, 可选
数字分子的非理性部分（判别器）
- sint, 可选
无理部分的系数
参考文献
[1][2]K. Rosen. Elementary Number theory and its applications. Addison-Wesley, 3 Sub edition, pages 379-381, January 1992.
示例
>>> from sympy.ntheory.continued_fraction import continued_fraction_periodic >>> continued_fraction_periodic(3, 2, 7) [2, [1, 4, 1, 1]]
黄金比例具有最简单的连分数展开：
>>> continued_fraction_periodic(1, 2, 5) [[1]]
如果判别式为零或是一个完全平方数，那么这个数将是一个有理数：
>>> continued_fraction_periodic(4, 3, 0) [1, 3] >>> continued_fraction_periodic(4, 3, 49) [3, 1, 2]
- sympy.ntheory.continued_fraction.continued_fraction_reduce(cf)[源代码][源代码]¶
将连分数简化为有理数或二次无理数。
从其终止或周期性的连分数展开中计算有理数或二次无理数。连分数展开（cf）应作为一个终止的迭代器提供，该迭代器提供展开的项。对于终止的连分数，这等价于
list(continued_fraction_convergents(cf))[-1]，只是稍微更高效一些。如果展开有一个重复部分，应从迭代器返回一个包含重复项的列表作为最后一个元素。这是由 continued_fraction_periodic 返回的格式。对于二次无理数，返回找到的最大解，如果分数是标准形式（所有项为正，可能除了第一个项），这通常是所寻求的那个解。
示例
>>> from sympy.ntheory.continued_fraction import continued_fraction_reduce >>> continued_fraction_reduce([1, 2, 3, 4, 5]) 225/157 >>> continued_fraction_reduce([-2, 1, 9, 7, 1, 2]) -256/233 >>> continued_fraction_reduce([2, 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8]).n(10) 2.718281835 >>> continued_fraction_reduce([1, 4, 2, [3, 1]]) (sqrt(21) + 287)/238 >>> continued_fraction_reduce([[1]]) (1 + sqrt(5))/2 >>> from sympy.ntheory.continued_fraction import continued_fraction_periodic >>> continued_fraction_reduce(continued_fraction_periodic(8, 5, 13)) (sqrt(13) + 8)/5
- sympy.ntheory.digits.count_digits(n, b=10)[源代码][源代码]¶
返回一个字典，其键是给定基数
b中n的数字，键表示数字中出现的数字，值表示该数字出现的次数。示例
>>> from sympy.ntheory import count_digits
>>> count_digits(1111339) {1: 4, 3: 2, 9: 1}
返回的数字总是以十进制表示，但数字本身可以用Python理解的任何格式输入；如果数字的基数不是10，也可以指定其基数：
>>> n = 0xFA; n 250 >>> count_digits(_) {0: 1, 2: 1, 5: 1} >>> count_digits(n, 16) {10: 1, 15: 1}
默认字典将为数字中未出现的任何数字返回 0。例如，在
77!中哪些数字出现了 7 次：>>> from sympy import factorial >>> c77 = count_digits(factorial(77)) >>> [i for i in range(10) if c77[i] == 7] [1, 3, 7, 9]
- sympy.ntheory.digits.digits(n, b=10, digits=None)[源代码][源代码]¶
返回
n在基数b中的数字列表。列表的第一个元素是b（如果n为负数，则为-b）。- 参数:
- n: 整数
返回其数字的数字。
- b: 整数
数字计算的基数。
- digits: 整数 (或 None 表示所有数字)
要返回的数字位数（必要时用零填充）。
示例
>>> from sympy.ntheory.digits import digits >>> digits(35) [10, 3, 5]
如果数字是负数，负号将被放置在基数上（这是返回列表中的第一个元素）：
>>> digits(-35) [-10, 3, 5]
可以选择10以外的基数（且大于1），通过
b来选择：>>> digits(27, b=2) [2, 1, 1, 0, 1, 1]
如果需要特定数量的数字，请使用
digits关键字：>>> digits(35, digits=4) [10, 0, 0, 3, 5]
- sympy.ntheory.digits.is_palindromic(n, b=10)[源代码][源代码]¶
如果
n在给定的基数b中从左到右或从右到左读取时相同，则返回 True。示例
>>> from sympy.ntheory import is_palindromic
>>> all(is_palindromic(i) for i in (-11, 1, 22, 121)) True
第二个参数允许你测试其他进制中的数字。例如，88 在十进制中是回文的，但在八进制中不是：
>>> is_palindromic(88, 8) False
另一方面，一个数字在八进制中可能是回文数，但在十进制中不是：
>>> 0o121, is_palindromic(0o121) (81, False)
或者它在两种基数下都是回文的：
>>> oct(121), is_palindromic(121, 8) and is_palindromic(121) ('0o171', True)
- sympy.ntheory.egyptian_fraction.egyptian_fraction(r, algorithm='Greedy')[源代码][源代码]¶
返回一个埃及分数展开 [1] 的给定有理数 \(r\) 的分母列表。
- 参数:
- rRational 或 (p, q)
一个正的有理数，
p/q。- 算法{ “贪心”, “格雷厄姆·朱厄特”, “竹内”, “戈伦布” }, 可选
表示要使用的算法（默认是“贪心”）。
注释
目前支持以下算法：
贪心算法
也称为斐波那契-西尔维斯特算法 [2]。在每一步中，提取小于目标的最大单位分数，并用余数替换目标。
它有一些独特的属性：
给定 \(p/q\) 为最简形式，生成一个最大长度为 \(p\) 的展开式。即使分子变大，项数也很少超过几个。
使用最少的内存。
这些项可以膨胀（标准例子有 5/121 和 31/311）。分母在每一步最多平方增长（双指数增长），通常表现为单指数增长。
格雷厄姆-朱伊特算法
由Graham和Jewett结果提出的算法。注意，这有爆炸的倾向：结果扩展的长度总是
2**(x/gcd(x, y)) - 1。参见 [3]。Takenouchi 算法
Takenouchi (1921) 提出的算法。与 Graham-Jewett 算法仅在处理重复项上有所不同。参见 [3]。
Golomb 算法
Golumb (1962) 提出的方法，使用模运算和逆元。它产生的结果与 Bleicher (1972) 提出的使用连分数的方法相同。参见 [4]。
如果给定的有理数大于或等于1，则使用求和调和序列1/1 + 1/2 + 1/3 + …的贪心算法，取该序列的所有单位分数，直到再增加一个单位分数会大于给定的数。这个分母列表会添加到使用请求算法对余数处理的结果之前。例如，如果r是8/3，使用贪心算法，我们得到[1, 2, 3, 4, 5, 6, 7, 14, 420]，其中序列的开头部分，[1, 2, 3, 4, 5, 6, 7]是调和序列求和到363/140，留下余数31/420，通过贪心算法得到[14, 420]。egyptian_fraction(Rational(8, 3), “Golomb”)的结果是[1, 2, 3, 4, 5, 6, 7, 14, 574, 2788, 6460, 11590, 33062, 113820]，依此类推。
参考文献
[1]示例
>>> from sympy import Rational >>> from sympy.ntheory.egyptian_fraction import egyptian_fraction >>> egyptian_fraction(Rational(3, 7)) [3, 11, 231] >>> egyptian_fraction((3, 7), "Graham Jewett") [7, 8, 9, 56, 57, 72, 3192] >>> egyptian_fraction((3, 7), "Takenouchi") [4, 7, 28] >>> egyptian_fraction((3, 7), "Golomb") [3, 15, 35] >>> egyptian_fraction((11, 5), "Golomb") [1, 2, 3, 4, 9, 234, 1118, 2580]
- sympy.ntheory.bbp_pi.pi_hex_digits(n, prec=14)[源代码][源代码]¶
返回一个包含
prec（默认 14）位数的字符串，从十六进制π的第 n 位开始。位数从 0 开始计数，小数点不计数，因此对于 n = 0，返回的值以 3 开头；n = 1 对应于小数点后的第一位（在十六进制中是 2）。- 参数:
- n非负整数
- prec非负整数。默认值 = 14
- 返回:
- str : 返回一个包含
prec位数的字符串返回一个包含 从π的第n位十六进制数开始。如果
prec= 0，返回空字符串。
- str : 返回一个包含
- Raises:
- ValueError
如果
n< 0 或prec< 0。或者n或prec不是整数。
参考文献
示例
>>> from sympy.ntheory.bbp_pi import pi_hex_digits >>> pi_hex_digits(0) '3243f6a8885a30' >>> pi_hex_digits(0, 3) '324'
这些与以下结果一致
>>> import math >>> hex(int(math.pi * 2**((14-1)*4))) '0x3243f6a8885a30' >>> hex(int(math.pi * 2**((3-1)*4))) '0x324'
ECM 功能¶
\(ecm\) 函数是一种次指数因式分解算法，能够在几秒钟内轻松分解大约35位数的数字。\(ecm\) 的时间复杂度取决于该数的最小适当因子。因此，即使数字非常大，但如果其因子相对较小，\(ecm\) 也可以轻松分解它们。例如，我们取 \(N\)，其因子为15位数 \(15154262241479\)、\(15423094826093\)、\(799333555511111\)、\(809709509409109\)、\(888888877777777\)、\(914148152112161\)。现在 \(N\) 是一个87位数的数字。\(ECM\) 大约需要47秒来分解这个数字。
- sympy.ntheory.ecm.ecm(
- n,
- B1=10000,
- B2=100000,
- max_curve=200,
- seed=1234,
使用Lenstra的椭圆曲线方法进行因式分解。
此函数反复调用
_ecm_one_factor来计算 n 的因子。首先使用试除法取出所有小因子。然后使用_ecm_one_factor一次计算一个因子。- 参数:
- n待分解的数
- B1阶段 1 边界。必须是偶数。
- B2阶段 2 边界。必须是偶数。
- max_curve生成的曲线最大数量
- 种子初始化伪随机数生成器
示例
>>> from sympy.ntheory import ecm >>> ecm(25645121643901801) {5394769, 4753701529} >>> ecm(9804659461513846513) {4641991, 2112166839943}
示例¶
>>> from sympy.ntheory import ecm
>>> ecm(7060005655815754299976961394452809, B1=100000, B2=1000000)
{6988699669998001, 1010203040506070809}
>>> ecm(122921448543883967430908091422761898618349713604256384403202282756086473494959648313841, B1=100000, B2=1000000)
{15154262241479,
15423094826093,
799333555511111,
809709509409109,
888888877777777,
914148152112161}
QS 函数¶
\(qs\) 函数是一种次指数分解算法，是处理100位以内数字的最快分解算法。\(qs\) 的时间复杂度取决于数字的大小，因此当数字包含大因子时使用。由于这个原因，在分解数字时，首先使用 \(ecm\) 获取大约15位的小因子，然后使用 \(qs\) 获取更大的因子。
对于分解 \(2709077133180915240135586837960864768806330782747\) 这个半素数（由两个25位数因子组成），\(qs\) 能够在约248秒内完成分解。
- sympy.ntheory.qs.qs(N, prime_bound, M, ERROR_TERM=25, seed=1234)[源代码][源代码]¶
使用自初始化二次筛法进行因式分解。在SIQS中，设N为待分解的数，且N不应是完美幂。如果我们找到两个整数，使得
X**2 = Y**2 modN且X != +-Y modN，那么 \(gcd(X + Y, N)\) 将揭示N的一个真因子。为了找到这些整数X和Y，我们尝试找到形式为 t**2 = u modN 的关系，其中u是一些小质数的乘积。如果我们有足够多的这些关系，那么我们可以形成(t1*t2...ti)**2 = u1*u2...ui modN，使得右边是一个平方，从而我们找到了一个X**2 = Y**2 modN的关系。这里，进行了多项优化，如使用多个多项式进行筛选、快速在多项式之间切换以及使用部分关系。使用部分关系可以使分解速度提高2倍。
- 参数:
- N待分解的数
- prime_bound因子基中素数的 上界
- MSieve 区间
- 错误术语用于检查平滑度的误差项
- 阈值因式分解的额外平滑关系
- 种子生成伪素数
参考文献
[2]https://www.rieselprime.de/ziki/自初始化二次筛选法
示例
>>> from sympy.ntheory import qs >>> qs(25645121643901801, 2000, 10000) {5394769, 4753701529} >>> qs(9804659461513846513, 2000, 10000) {4641991, 2112166839943}
示例¶
>>> from sympy.ntheory import qs
>>> qs(5915587277*3267000013, 1000, 10000)
{3267000013, 5915587277}