数论#
N理论类参考#
- class sympy.ntheory.generate.Sieve(sieve_interval=1000000)[源代码]#
A list of prime numbers, implemented as a dynamically growing sieve of Eratosthenes. When a lookup is requested involving an odd number that has not been sieved, the sieve is automatically extended up to that number. Implementation details limit the number of primes to
2^32-1.实例
>>> 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)[源代码]#
Grow the sieve to cover all primes <= 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 ：整数
实例
>>> 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])
笔记
如果列表太短，则会延长50%，因此很可能会比要求的长。
- 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)[源代码]#
Generate all prime numbers in the range [2, a) or [a, b).
实例
>>> from sympy import sieve, prime
All primes less than 19:
>>> print([i for i in sieve.primerange(19)]) [2, 3, 5, 7, 11, 13, 17]
All primes greater than or equal to 7 and less than 19:
>>> print([i for i in sieve.primerange(7, 19)]) [7, 11, 13, 17]
All primes through the 10th prime
>>> list(sieve.primerange(prime(10) + 1)) [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
N理论函数参考#
- sympy.ntheory.generate.prime(nth)[源代码]#
Return the nth prime, with the primes indexed as prime(1) = 2, prime(2) = 3, etc.... The nth prime is approximately \(n\log(n)\).
Logarithmic integral of \(x\) is a pretty nice approximation for number of primes \(\le x\), i.e. li(x) ~ pi(x) In fact, for the numbers we are concerned about( x<1e11 ), li(x) - pi(x) < 50000
另外，对于可以用这个函数计算的数，可以安全地假设li（x）>pi（x）。
在这里，我们使用二元搜索找到最小整数m，使得li（m）>n。现在pi（m-1）<li（m-1）<=n，
利用primepi函数求π（m-1）。
从m开始，我们必须找到更多的n-pi（m-1）素数。
对于这个实现可以处理的输入，我们将不得不测试至多10**5个数字的素性，以得到我们的答案。
实例
>>> from sympy import prime >>> prime(10) 29 >>> prime(1) 2 >>> prime(100000) 1299709
参见
sympy.ntheory.primetest.isprime如果n是素数测试
primerange生成给定范围内的所有素数
primepi返回小于或等于n的素数
工具书类
[R648]https://en.wikipedia.org/wiki/Prime_number#u定理
[R649]https://en.wikipedia.org/wiki/Prime_number#u定理
- sympy.ntheory.generate.primepi(n)[源代码]#
表示素数计数函数pi（n）=小于或等于n的素数数。
自 1.13 版本弃用: The
primepifunction is deprecated. Usesympy.functions.combinatorial.numbers.primepiinstead. See its documentation for more information. See Relocate symbolic functions from ntheory to functions for details.算法描述：
在筛分法中，除p本身外，我们除去素数p的所有倍数。
设phi（i，j）是从小于或等于j的素数中筛选出的整数2<=k<=i的个数。显然，pi（n）=phi（n，sqrt（n））
如果j不是素数，φ（i，j）=φ（i，j-1）
如果j是一个素数，我们去掉所有最小素数因子为j的数（除了j）。
Let \(x= j \times a\) be such a number, where \(2 \le a \le i / j\) Now, after sieving from primes \(\le j - 1\), a must remain (because x, and hence a has no prime factor \(\le j - 1\)) Clearly, there are phi(i / j, j - 1) such a which remain on sieving from primes \(\le j - 1\)
Now, if a is a prime less than equal to j - 1, \(x= j \times a\) has smallest prime factor = a, and has already been removed(by sieving from a). So, we do not need to remove it again. (Note: there will be pi(j - 1) such x)
因此，要去掉的x的个数是：φ（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：
φ（a，b）=φ（a，b-1），如果b不是素数φ（a，b）=φ（a，b-1）-φ（a/b，b-1）+φ（b-1，b-1），如果b是素数
Clearly a is always of the form floor(n / k), which can take at most \(2\sqrt{n}\) values. Two arrays arr1,arr2 are maintained arr1[i] = phi(i, j), arr2[i] = phi(n // i, j)
最后答案是arr2 [1]
实例
>>> from sympy import primepi, prime, prevprime, isprime >>> primepi(25) 9
So there are 9 primes less than or equal to 25. Is 25 prime?
>>> isprime(25) False
It is not. So the first prime less than 25 must be the 9th prime:
>>> prevprime(25) == prime(9) True
参见
sympy.ntheory.primetest.isprime如果n是素数测试
primerange生成给定范围内的所有素数
prime返回第n个素数
- sympy.ntheory.generate.nextprime(n, ith=1)[源代码]#
返回大于n的第i个素数。
- 参数:
n ：整数
ith : positive integer
- 返回:
int : Return the ith prime greater than n
- 加薪:
ValueError
If
ith <= 0. Ifnorithis not an integer.
笔记
潜在素数位于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
参见
prevprime比最大的n素数小
primerange生成给定范围内的所有素数
- sympy.ntheory.generate.prevprime(n)[源代码]#
返回小于n的最大素数。
笔记
潜在素数位于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)]
参见
nextprime返回大于n的第i个素数
primerange生成给定范围内的所有素数
- sympy.ntheory.generate.primerange(a, b=None)[源代码]#
Generate a list of all prime numbers in the range [2, a), or [a, b).
如果默认筛选中存在范围，则将从中返回值；否则将返回值，但不会修改筛选。
实例
>>> from sympy import primerange, prime
All primes less than 19:
>>> list(primerange(19)) [2, 3, 5, 7, 11, 13, 17]
All primes greater than or equal to 7 and less than 19:
>>> list(primerange(7, 19)) [7, 11, 13, 17]
All primes through the 10th prime
>>> list(primerange(prime(10) + 1)) [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
筛选方法primerange通常更快，但由于筛子存储值，它将占用更多内存。Sieve的默认实例名为Sieve，可用于：
>>> from sympy import sieve >>> list(sieve.primerange(1, 30)) [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
笔记
关于给定范围内质数出现的一些著名猜想是 [1] ：
- 孪生素数：虽然通常不是，但下面将给出2个素数
- 无数次：
素描（6 n - 1, 6 n+2）
- 勒让德：下面的总是至少产生一个素数
素数范围（n 2，（n+1） （1+2）
- 贝特朗（证明）：总有一个质数在范围内
素数范围（n，2*n）
- 布罗卡：这个范围内至少有四个质数
素数范围（素数（n） 2，素数（n+1） 2）
素数之间的平均间隔是log（n） [2] ；质数之间的间隔可以任意大，因为复合数序列是任意大的，例如序列n中的数！+2，n！+3。。。n！+n都是复合的。
参见
工具书类
- sympy.ntheory.generate.randprime(a, b)[源代码]#
返回范围为[a，b）的随机素数。
Bertrand的假设保证了randprime（a，2*a）对于a>1总是成功的。
Note that due to implementation difficulties, the prime numbers chosen are not uniformly random. For example, there are two primes in the range [112, 128),
113and127, butrandprime(112, 128)returns127with a probability of 15/17.实例
>>> from sympy import randprime, isprime >>> randprime(1, 30) 13 >>> isprime(randprime(1, 30)) True
参见
primerange生成给定范围内的所有素数
工具书类
- sympy.ntheory.generate.primorial(n, nth=True)[源代码]#
返回前n个素数的乘积（默认值）或小于或等于n的素数的乘积（当
nth=False）实例
>>> 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
我们可以说素数是无穷大的，因为如果你取一组素数并将它们相乘（例如primorial），然后加上或减去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]
参见
primerange生成给定范围内的所有素数
- 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
又取种子四个，计算出亩数和λ项：
>>> 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]
There are 6 repeating values after the first 3.
如果一个序列被怀疑比你希望的长，
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个复合数，复合数的索引为复合数（1）=4，复合数（2）=6，等等。。。。
实例
>>> from sympy import composite >>> composite(36) 52 >>> composite(1) 4 >>> composite(17737) 20000
参见
sympy.ntheory.primetest.isprime如果n是素数测试
primerange生成给定范围内的所有素数
primepi返回小于或等于n的素数
prime返回第n个素数
compositepi返回小于或等于n的正合成数的个数
- sympy.ntheory.generate.compositepi(n)[源代码]#
返回小于或等于n的正合成数的个数。第一个正合成数为4，即compositepi（4）=1。
实例
>>> from sympy import compositepi >>> compositepi(25) 15 >>> compositepi(1000) 831
参见
sympy.ntheory.primetest.isprime如果n是素数测试
primerange生成给定范围内的所有素数
prime返回第n个素数
primepi返回小于或等于n的素数
composite返回第n个组合数
- 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的功率平滑度
列表将根据平滑度（默认值）进行排序，如果幂为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}
输出逻辑表如下：
视觉的
输入
对
假
其他
双关语
STR
元组
STR
STR
STR
元组
双关语
元组
STR
元组
STR
N号
STR
元组
元组
骡子
STR
元组
元组
参见
- sympy.ntheory.factor_.multiplicity(p, n)[源代码]#
求最大整数m，使p**m除以n。
实例
>>> 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)[源代码]#
Return
(b, e)such thatn==b**eifnis a unique perfect power withe > 1, elseFalse(e.g. 1 is not a perfect power). A ValueError is raised ifnis not Rational.默认情况下，基函数是递归分解的，而指数则是最大的
e正在寻找。如果big=False那么最小的可能e（因此是质数）将被选中。如果
factor=True然后同时分解n由于查找因子指示的唯一可能的根n. 这在默认情况下是正确的，因为在寻找完美功率的过程中，只会测试一些小因素。对.的使用
candidates主要供内部使用；如果提供，则返回FALSEn不能将其中一个候选者写为幂，并且不会尝试因式分解(超出因数2的测试)。实例
>>> from sympy import perfect_power, Rational >>> perfect_power(16) (2, 4) >>> perfect_power(16, big=False) (4, 2)
Negative numbers can only have odd perfect powers:
>>> perfect_power(-4) False >>> perfect_power(-8) (-2, 3)
Rationals are also recognized:
>>> perfect_power(Rational(1, 2)**3) (1/2, 3) >>> perfect_power(Rational(-3, 2)**3) (-3/2, 3)
笔记
知道整数是否是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. 假设INT将被假定为。第一个大于计算的最大可能指数的值将表示例程失败。>>> 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)
- 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将被供应；供应a如果提供了F，将被忽略。由这种函数生成的数字序列通常有一个a开头的数字，然后循环回到那个数字，并开始重复这个序列，例如1、2、3、4、5、3、4、5——这个前导和循环看起来有点像希腊字母rho，因此它的名字是“rho”。
对于给定函数，可以获得非常不同的先导循环值，因此允许重试是一个好主意：
>>> 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
Here is an explicit example where there is a three element leadup to a sequence of 3 numbers (11, 14, 4) that then repeat:
>>> 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个第2个数字，例如第1个和第2个、第2个和第4个、第3个和第6个，直到检测到循环已被遍历为止。在rho找到一个因子或报告失败之前，循环可能需要数千步。如果
max_steps，则迭代将在指定的步骤数之后因失败而取消。实例
>>> 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
工具书类
[R654]Richard Crandall和Carl Pomerance（2005），“素数：计算视角”，Springer，第2版，229-231
- 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）=减小（ilcm，范围（2，B+1））。
搜索幂平滑度小于的偶数旁边的因子
B. 选择一个更大的B会增加找到一个更大因子的可能性，但需要更长的时间。是否找到系数n取决于a偶数的幂光滑度小于因子p（因此得名p-1）。虽然有些关于什么是好的讨论
a有些描述很难解释。在模块化数学下面引用的站点说明，如果gcd（a M - 1, n) = N then a M%q**r是N的每一个素数幂因子的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
If we attempt to increase B to 256 we find that it does not work:
>>> pollard_pm1(n, B=256) >>>
但是如果
a改变后，我们发现只有257的倍数有效，例如：>>> pollard_pm1(n, B=256, a=257) 1009
Checking different
avalues shows that all the ones that did not work had a gcd value not equal tonbut equal to one of the factors:>>> 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其中一个可能会产生一个因子。实例
With the default smoothness bound, this number cannot be cracked:
>>> 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达到B-pow值1787，该数字才被破解；
>>> pollard_pm1(21477639576571, B=1786) >>> pollard_pm1(21477639576571, B=1787) 4410317
The B value has to do with the factors of the number next to the divisor, not the divisors themselves. A worst case scenario is that the number next to the factor p has a large prime divisisor or is a perfect power. If these conditions apply then the power-smoothness will be about p/2 or p. The more realistic is that there will be a large prime factor next to p requiring a B value on the order of p/2. Although primes may have been searched for up to this level, the p/2 is a factor of p - 1, something that we do not know. The modular.math reference below states that 15% of numbers in the range of 10**15 to 15**15 + 10**4 are 10**6 power smooth so a B of 10**6 will fail 85% of the time in that range. From 10**8 to 10**8 + 10**3 the percentages are nearly reversed...but in that range the simple trial division is quite fast.
工具书类
- 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)returns the empty factorization,{}factorint(0)returns{0:1}factorint(-n)adds-1:1to the factors and then factorsn
部分因子分解：
如果
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}
输出逻辑表如下：
输入
对
假
其他
双关语
骡子
双关语
骡子
N号
骡子
双关语
双关语
骡子
骡子
双关语
双关语
笔记
算法：
函数在多个算法之间切换。试算部很快就可以找到小因子（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的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的rho方法use_pm1：切换使用Pollard的p-1方法verbose：切换进度的详细打印multiple：切换返回因子列表或dictvisual：切换输出的产品形式
- sympy.ntheory.factor_.primefactors(n, limit=None, verbose=False, **kwargs)[源代码]#
返回n的素数因子的排序列表，忽略多重性和如果限制设置得太低而无法进行完全因式分解的任何组合因子。与factorint（）不同，primefactors（）不返回-1或0。
- 参数:
n ：整数
limit, verbose, **kwargs :
Additional keyword arguments to be passed to
factorint. Sincekwargsis new in version 1.13,limitandverboseare retained for compatibility purposes.- 返回:
list(int) : List of prime numbers dividing
n
实例
>>> 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)[源代码]#
默认情况下，返回从1..n排序的n的所有除数。如果发电机为
True返回一个无序的生成器。如果有许多素数因子（计算重复因子），n的除数可能很大。如果只需要因子的数量，则使用除数_count（n）。
实例
>>> 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]
笔记
这是对Tim Peters稍作修改的版本，参考：https://stackoverflow.com/questions/1010381/python-factorization
- sympy.ntheory.factor_.proper_divisors(n, generator=False)[源代码]#
返回除n以外的n的所有除数，默认排序。如果发电机
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是真的那么除数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)[源代码]#
默认情况下，返回从1..n排序的n的所有酉除数。如果发电机
True返回一个无序的生成器。如果有许多素数因子，n的酉除数可能很大。如果只需要酉除数，则使用udivisoru 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)[源代码]#
默认情况下，返回从1..n排序的n的所有反病毒程序。
Antidivisors [R661] of n are numbers that do not divide n by the largest possible margin. If generator is True an unordered generator is returned.
实例
>>> 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)[源代码]#
Return the number of antidivisors [R662] of
n.- 参数:
n ：整数
实例
>>> from sympy.ntheory.factor_ import antidivisor_count >>> antidivisor_count(13) 4 >>> antidivisor_count(27) 5
工具书类
- sympy.ntheory.factor_.totient(n)[源代码]#
计算欧拉函数φ（n）
自 1.13 版本弃用: The
totientfunction is deprecated. Usesympy.functions.combinatorial.numbers.totientinstead. See its documentation for more information. See Relocate symbolic functions from ntheory to functions for details.totient(n)或 \(\phi(n)\) 是正整数的数目 \(\leq\) 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 版本弃用: The
reduced_totientfunction is deprecated. Usesympy.functions.combinatorial.numbers.reduced_totientinstead. See its documentation for more information. See Relocate symbolic functions from ntheory to functions for details.reduced_totient(n)或 \(\lambda(n)\) 最小的m>0是这样的吗 \(k^m \equiv 1 \mod n\) 对于所有k，相对质数对n。实例
>>> 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)[源代码]#
计算除数函数 \(\sigma_k(n)\) 对于正整数n
自 1.13 版本弃用: The
divisor_sigmafunction is deprecated. Usesympy.functions.combinatorial.numbers.divisor_sigmainstead. See its documentation for more information. See Relocate symbolic functions from ntheory to functions for details.divisor_sigma(n, k)is equal tosum([x**k for x in divisors(n)])如果n的素因式分解是：
\[n=\prod{i=1}^\omega p\u i^{m\u i}，\]然后
\[\西格玛（n）=\prod{i=1}^\omega（1+p_i^k+p_i^{2k}+\cdots\]- 参数:
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)[源代码]#
求酉除数函数 \(\sigma_k^*(n)\) 对于正整数n
自 1.13 版本弃用: The
udivisor_sigmafunction is deprecated. Usesympy.functions.combinatorial.numbers.udivisor_sigmainstead. See its documentation for more information. See Relocate symbolic functions from ntheory to functions for details.udivisor_sigma(n, k)is equal tosum([x**k for x in udivisors(n)])如果n的素因式分解是：
\[n=\prod{i=1}^\omega p\u i^{m\u i}，\]然后
\[\西格玛（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，t）= \(core_t(n)\) 正整数n的
core_2(n)等于n的无平方部分如果n的素因式分解是：
\[n=\prod{i=1}^\omega p\u i^{m\u i}，\]然后
\[核心（n）=\prod{i=1}^\omega p_i^{m_i\mod t}。\]- 参数:
n ：整数
t ：整数
core（n，t）计算n的第t个无功部分
core(n, 2)is the squarefree part ofncore(n, 3)is the cubefree part ofnt的默认值为2。
实例
>>> from sympy.ntheory.factor_ import core >>> core(24, 2) 6 >>> core(9424, 3) 1178 >>> core(379238) 379238 >>> core(15**11, 10) 15
工具书类
[R669]https://en.wikipedia.org/wiki/Square-free_integer#Squarefree_核心
- sympy.ntheory.factor_.digits(n, b=10, digits=None)[源代码]#
返回的数字列表
n在底部b. 列表中的第一个元素是b（或）-b如果n是否定的）。- 参数:
n： 整数
返回其位数的数字。
b： 整数
计算位数的基数。
位数：整数（或所有位数均为无）
要返回的位数（如有必要，用零填充）。
实例
>>> 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 版本弃用: The
primenufunction is deprecated. Usesympy.functions.combinatorial.numbers.primenuinstead. See its documentation for more information. See Relocate symbolic functions from ntheory to functions for details.如果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 版本弃用: The
primeomegafunction is deprecated. Usesympy.functions.combinatorial.numbers.primeomegainstead. See its documentation for more information. See Relocate symbolic functions from ntheory to functions for details.如果n的素因式分解是：
\[n=\prod{i=1}^k p_i^{m_i}，\]然后
primeomega(n)或 \(\Omega(n)\) 是：\[\ω（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)[源代码]#
返回指数
i对于第n个梅森素数（它有 \(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)[源代码]#
返回true
n是一个完全数，否则为假。一个完全数等于它的正的，真除数的和。
实例
>>> 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)[源代码]#
返回true
n是一个丰富的数字，否则为假。一个富足数小于它的正真除数之和。
实例
>>> from sympy.ntheory.factor_ import is_abundant >>> is_abundant(20) True >>> is_abundant(15) False
工具书类
- sympy.ntheory.factor_.is_deficient(n)[源代码]#
返回true
n是一个亏数，否则为假。一个亏数大于它的正真除数之和。
实例
>>> from sympy.ntheory.factor_ import is_deficient >>> is_deficient(20) False >>> is_deficient(15) True
工具书类
- sympy.ntheory.factor_.is_amicable(m, n)[源代码]#
如果数字 \(m\) 和 \(n\) 是“友好的”，否则是假的。
友好数是两个相互关联的数，它们的真除数之和等于另一个数。
实例
>>> 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)[源代码]#
Returns True if the numbers \(n\) is Carmichael number, else False.
- 参数:
n : Integer
工具书类
- sympy.ntheory.factor_.find_carmichael_numbers_in_range(x, y)[源代码]#
Returns a list of the number of Carmichael in the range
- sympy.ntheory.factor_.find_first_n_carmichaels(n)[源代码]#
Returns the first n Carmichael numbers.
- 参数:
n : Integer
- 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，这样f=v逖i mod m逖i，对于v和m中的每一对，如果
symmetric如果为False，则返回一个正整数，否则| f|将小于或等于模的LCM，因此f可能为负。如果模不共充，如果/当结果测试发现不正确时，将返回正确的结果。如果没有解决办法，这个结果就没有了。
关键词
check如果已知模是互质的，则可以设置为False。实例
作为一个例子，考虑一组残留物
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相反，而解_-crt的同余取余数、模对。
程序员注：不是检查所有模对是否共享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]
The following two codes have the same result.
>>> crt(m, v) (639985, 912285)
>>> mm, e, s = crt1(m) >>> crt2(m, v, mm, e, s) (639985, 912285)
However, it is faster when we want to fix
mand compute for multiplev, i.e. the following cases:>>> 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)[源代码]#
第二部分中国余数定理，用于多重应用。
See
crt1for usage.实例
>>> 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有剩余的ai当它除以mi何处ai和mi以成对的形式给出该函数：（（a1，m1），（a2，m2），…）。如果没有解决方案，则返回“无”。否则返回n以及它的模量。这个
mi值不必是辅素数。如果已知模不是余素数，则提示check可以设置为False（默认值为True），并且将跳过通过crt（）检查更快的解决方案（当模块为co-prime时有效）。如果暗示
symmetric为True（默认值为False），则n将在模量的1/2范围内，可能为负值。实例
>>> from sympy.ntheory.modular import solve_congruence
2模3，3模5和2模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)
参见
crt实现中国剩余定理的高级程序
- 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)[源代码]#
返回作为Pascal三角形行的二项式系数列表。
实例
>>> 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.实例
>>> 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}
笔记
该算法基于以下结果：
\[\比诺姆{n}{ku 1，\ldots，k}=\]由Yann Laigle Chapuy提供给Sage的代码，经作者许可复制。
- 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 版本弃用: The
npartitionsfunction is deprecated. Usesympy.functions.combinatorial.numbers.partitioninstead. See its documentation for more information. See Relocate symbolic functions from ntheory to functions for details.P(n) is computed using the Hardy-Ramanujan-Rademacher formula [R679].
The correctness of this implementation has been tested through \(10^{10}\).
实例
>>> from sympy.functions.combinatorial.numbers import partition >>> partition(25) 1958
工具书类
- sympy.ntheory.primetest.is_fermat_pseudoprime(n, a)[源代码]#
Returns True if
nis prime or is an odd composite integer that is coprime toaand satisfy the modular arithmetic congruence relation:\[a^{n-1} \equiv 1 \pmod{n}\]（其中mod是指模运算）。
- 参数:
n : Integer
nis a positive integer.a : Integer
ais a positive integer.aandnshould be relatively prime.- 返回:
bool : If
nis prime, it always returnsTrue.The composite number that returns
Trueis called an Fermat pseudoprime.
实例
>>> 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)[源代码]#
Returns True if
nis prime or is an odd composite integer that is coprime toaand satisfy the modular arithmetic congruence relation:\[a^{(n-1)/2} \equiv \pm 1 \pmod{n}\]（其中mod是指模运算）。
- 参数:
n : Integer
nis a positive integer.a : Integer
ais a positive integer.aandnshould be relatively prime.- 返回:
bool : If
nis prime, it always returnsTrue.The composite number that returns
Trueis called an Euler pseudoprime.
实例
>>> 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)[源代码]#
Returns True if
nis prime or is an odd composite integer that is coprime toaand satisfy the modular arithmetic congruence relation:\[a^{(n-1)/2} \equiv \left(\frac{a}{n}\right) \pmod{n}\]（其中mod是指模运算）。
- 参数:
n : Integer
nis a positive integer.a : Integer
ais a positive integer.aandnshould be relatively prime.- 返回:
bool : If
nis prime, it always returnsTrue.The composite number that returns
Trueis called an Euler-Jacobi pseudoprime.
实例
>>> 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)[源代码]#
如果n==a，则返回True a表示某个整数a，否则为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强伪素数测试。
实例
>>> from sympy.ntheory.primetest import mr >>> mr(1373651, [2, 3]) False >>> mr(479001599, [31, 73]) True
工具书类
[R684]Richard Crandall和Carl Pomerance（2005），“素数：计算视角”，Springer，第2版，135-138
A list of thresholds and the bases they require are here: https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test#Deterministic_variants
- sympy.ntheory.primetest.is_lucas_prp(n)[源代码]#
用Selfridge参数进行标准Lucas合成试验。如果n肯定是复合的，则返回False；如果n是Lucas可能素数，则返回True。
这通常与米勒-拉宾试验结合使用。
实例
>>> 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
工具书类
[R685]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
[R686]OEIS A217120：卢卡斯伪素数https://oeis.org/A217120
- sympy.ntheory.primetest.is_strong_lucas_prp(n)[源代码]#
Selfridge参数的强Lucas合成性检验。如果n肯定是复合的，则返回False；如果n是强Lucas或然素数，则返回True。
这通常与Miller-Rabin测试结合使用，尤其是与M-rbase 2结合使用时，会产生强大的BPSW测试。
实例
>>> 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
工具书类
[R688]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
[R689]OEIS A217255：强卢卡斯伪素数https://oeis.org/A217255
- sympy.ntheory.primetest.is_extra_strong_lucas_prp(n)[源代码]#
Extra Strong Lucas compositeness test. Returns False if n is definitely composite, and True if n is an "extra strong" Lucas probable prime.
The parameters are selected using P = 3, Q = 1, then incrementing P until (D|n) == -1. The test itself is as defined in [R692], from the Mo and Jones preprint. The parameter selection and test are the same as used in OEIS A217719, Perl's Math::Prime::Util, and the Lucas pseudoprime page on Wikipedia.
It is 20-50% faster than the strong test.
由于选取的参数不同，强Lucas伪素数与超强Lucas伪素数之间没有关系。特别是，一个不是另一个的子集。
实例
>>> 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
工具书类
[R692] (1,2)Jon Grantham, Frobenius Pseudoprimes, Math. Comp. Vol 70, Number 234 (2001), pp. 873-891, https://doi.org/10.1090%2FS0025-5718-00-01197-2
[R693]OEIS A217719：超强卢卡斯伪素数https://oeis.org/A217719
- sympy.ntheory.primetest.proth_test(n)[源代码]#
Test if the Proth number \(n = k2^m + 1\) is prime. where k is a positive odd number and \(2^m > k\).
- 参数:
n : Integer
nis Proth number- 返回:
bool : If
True, thennis the Proth prime- 加薪:
ValueError
If
nis not Proth number.
实例
>>> from sympy.ntheory.primetest import proth_test >>> proth_test(41) True >>> proth_test(57) False
工具书类
- sympy.ntheory.primetest.is_mersenne_prime(n)[源代码]#
返回true
n是梅森素数，否则为假。梅森素数是一个具有以下形式的素数 \(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是质数（真）还是非质数（假）。对于n<2^64，答案是确定的；n值越大，实际成为伪素数的概率就越小。
负数（例如-2）不被认为是素数。
第一步是寻找琐碎的因素，如果找到这些因素，可以快速返回。接下来，如果筛子足够大，在筛子上使用对分搜索。对于小数目，使用已知在其范围内没有反例的基数进行一组确定性米勒-拉宾试验。最后，如果数字大于2^64，则执行强BPSW测试。虽然这是一个可能的主要测试，我们相信存在反例，但没有已知的反例。
实例
>>> from sympy.ntheory import isprime >>> isprime(13) True >>> isprime(13.0) # limited precision False >>> isprime(15) False
笔记
此例程仅用于整数输入，而不是表示数字的数值表达式。浮点也被拒绝作为输入，因为它们表示精度有限的数字。虽然允许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
参见
sympy.ntheory.generate.primerange生成给定范围内的所有素数
sympy.functions.combinatorial.numbers.primepi返回小于或等于n的素数
sympy.ntheory.generate.prime返回第n个素数
工具书类
[R698]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
- sympy.ntheory.residue_ntheory.n_order(a, n)[源代码]#
返回的顺序
a模n.- 参数:
a ：整数
n : integer, n > 1. a and n should be relatively prime
- 返回:
int : the order of
amodulon- 加薪:
ValueError
If \(n \le 1\) or \(\gcd(a, n) \neq 1\). If
aornis not an integer.
解释
The order of
amodulonis the smallest integerksuch that \(a^k\) leaves a remainder of 1 withn.实例
>>> from sympy.ntheory import n_order >>> n_order(3, 7) 6 >>> n_order(4, 7) 3
参见
is_primitive_rootWe say that
ais a primitive root ofnwhen the order ofamodulonequalstotient(n)
- sympy.ntheory.residue_ntheory.is_primitive_root(a, p)[源代码]#
Returns True if
ais a primitive root ofp.- 参数:
a ：整数
p : integer,
p> 1.aandpshould be relatively prime- 返回:
bool : If True,
ais the primitive root ofp.- 加薪:
ValueError
If \(p \le 1\) or \(\gcd(a, p) \neq 1\). If
aorpis not an integer.
解释
ais said to be the primitive root ofpif \(\gcd(a, p) = 1\) and \(\phi(p)\) is the smallest positive number s.t.\(a^{\phi(p)} \equiv 1 \pmod{p}\).
where \(\phi(p)\) is Euler's totient function.
The primitive root of
pexist only for \(p = 2, 4, q^e, 2q^e\) (qis an odd prime). Hence, if it is not such ap, it returns False. To determine the primitive root, we need to know the prime factorization ofq-1. The hardness of the determination depends on this complexity.实例
>>> 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)[源代码]#
Returns a primitive root of
por None.- 参数:
p : integer, p > 1
smallest : if True the smallest primitive root is returned or None
- 返回:
int | None :
If the primitive root exists, return the primitive root of
p. If not, return None.- 加薪:
ValueError
If \(p \le 1\) or
pis not an integer.
解释
For the definition of primitive root, see the explanation of
is_primitive_root.The primitive root of
pexist only for \(p = 2, 4, q^e, 2q^e\) (qis an odd prime). Now, if we know the primitive root ofq, we can calculate the primitive root of \(q^e\), and if we know the primitive root of \(q^e\), we can calculate the primitive root of \(2q^e\). When there is no need to find the smallest primitive root, this property can be used to obtain a fast primitive root. On the other hand, when we want the smallest primitive root, we naively determine whether it is a primitive root or not.实例
>>> 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)[源代码]#
Find a root of
x**2 = a mod p.- 参数:
a ：整数
p ：正整数
all_roots 如果列表没有返回，则返回
笔记
如果没有根，则返回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'>)[源代码]#
Iterate over solutions to
x**2 = a mod p.- 参数:
a ：整数
p ：正整数
域 ：整数域，
int，ZZ或Integer
实例
>>> from sympy.ntheory.residue_ntheory import sqrt_mod_iter >>> list(sqrt_mod_iter(11, 43)) [21, 22]
参见
sqrt_modSame functionality, but you want a sorted list or only one solution.
- 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)[源代码]#
Find the solutions to
x**n = a mod p.- 参数:
a ：整数
n ：正整数
p ：正整数
all_roots ：如果False返回最小根，则返回根列表
- 返回:
list[int] | int | None :
solutions to
x**n = a mod p. The table of the output type is:all_roots
has roots
返回
对
Yes
list[int]
对
No
[]
假
Yes
利息
假
No
没有
- 加薪:
ValueError
If
a,norpis not integer. Ifnorpis not positive.
实例
>>> 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
工具书类
[R703]哈克曼《初等数理论》（2009），第76页
- sympy.ntheory.residue_ntheory.is_nthpow_residue(a, n, m)[源代码]#
返回true
x**n == a (mod m)有解决方案。工具书类
[R704]哈克曼《初等数理论》（2009），第76页
- sympy.ntheory.residue_ntheory.is_quad_residue(a, p)[源代码]#
Returns True if
a(modp) is in the set of squares modp, i.e a % p in set([i**2 % p for i in range(p)]).- 参数:
a ：整数
p ：正整数
- 返回:
bool : If True,
x**2 == a (mod p)has solution.- 加薪:
ValueError
If
a,pis not integer. Ifpis not positive.
实例
>>> from sympy.ntheory import is_quad_residue >>> is_quad_residue(21, 100) True
Indeed,
pow(39, 2, 100)would be 21.>>> is_quad_residue(21, 120) False
That is, for any integer
x,pow(x, 2, 120)is not 21.If
pis an odd prime, an iterative method is used to make the determination:>>> 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)[源代码]#
返回Legendre符号 \((a / p)\) .
自 1.13 版本弃用: The
legendre_symbolfunction is deprecated. Usesympy.functions.combinatorial.numbers.legendre_symbolinstead. See its documentation for more information. See Relocate symbolic functions from ntheory to functions for details.对于整数
a还有一个奇怪的质数p，Legendre符号定义为\[\genfrac（）{}{}{a}{p}=\begin{cases}\]- 参数:
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)[源代码]#
返回Jacobi符号 \((m / n)\) .
自 1.13 版本弃用: The
jacobi_symbolfunction is deprecated. Usesympy.functions.combinatorial.numbers.jacobi_symbolinstead. See its documentation for more information. See Relocate symbolic functions from ntheory to functions for details.对于任何整数
m以及任何正的奇数整数n雅可比符号被定义为勒让德符号对应的素数因子的乘积n：\[\genfrac（）{}{}{m}{n}=\]就像勒让德符号，如果雅各比符号 \(\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 版本弃用: The
mobiusfunction is deprecated. Usesympy.functions.combinatorial.numbers.mobiusinstead. See its documentation for more information. See Relocate symbolic functions from ntheory to functions for details.- 定义如下：
\(1\) 如果 \(n = 1\) .
\(0\) 如果 \(n\) 有一个平方素数。
\((-1)^k\) 如果 \(n\) 是一个无平方的正整数 \(k\) 素数因子。
它是数论和组合学中一个重要的乘法函数。它在数学级数、代数数论和物理学中都有应用（费米子算符用Mobius函数模型有很具体的实现）。
- 参数:
n ：正整数
实例
>>> from sympy.functions.combinatorial.numbers import mobius >>> mobius(13*7) 1 >>> mobius(1) 1 >>> mobius(13*7*5) -1 >>> mobius(13**2) 0
工具书类
[R706]托马斯科西“初等数论及其应用”
- sympy.ntheory.residue_ntheory.discrete_log(n, a, b, order=None, prime_order=None)[源代码]#
计算离散对数
a到基地去b模n.这是一个递归函数，将复合阶循环群中的离散对数问题归结为素阶循环群中的问题。
它根据问题的不同采用不同的算法（子组的顺序大小、素数顺序与否）：
试乘
婴儿大步
波拉德Rho
波利格·赫尔曼
实例
>>> from sympy.ntheory import discrete_log >>> discrete_log(41, 15, 7) 3
工具书类
[R708]“应用密码学手册”，Menezes，A.J.，Van，O.P.C.和Vanstone，S.A.（1997年）。
- sympy.ntheory.residue_ntheory.quadratic_congruence(a, b, c, n)[源代码]#
Find the solutions to \(a x^2 + b x + c \equiv 0 \pmod{n}\).
- 参数:
a : int
b : int
c : int
n ：内景
A positive integer.
- 返回:
list[int] :
A sorted list of solutions. If no solution exists,
[].
实例
>>> 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 []
参见
polynomial_congruenceSolve the polynomial congruence
- sympy.ntheory.residue_ntheory.polynomial_congruence(expr, m)[源代码]#
Find the solutions to a polynomial congruence equation modulo m.
- 参数:
expr : integer coefficient polynomial
m : positive integer
实例
>>> from sympy.ntheory import polynomial_congruence >>> from sympy.abc import x >>> expr = x**6 - 2*x**5 -35 >>> polynomial_congruence(expr, 6125) [3257]
参见
sympy.polys.galoistools.gf_csolvelow level solving routine used by this routine
- sympy.ntheory.residue_ntheory.binomial_mod(n, m, k)[源代码]#
Compute
binomial(n, m) % k.- 参数:
n : an integer
m : an integer
k : a positive integer
解释
Returns
binomial(n, m) % kusing a generalization of Lucas' Theorem for prime powers given by Granville [R709], in conjunction with the Chinese Remainder Theorem. The residue for each prime power is calculated in time O(log^2(n) + q^4*log(n)log(p) + q^4*p*log^3(p)).实例
>>> 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
工具书类
[R709] (1,2)Binomial coefficients modulo prime powers, Andrew Granville, Available: https://web.archive.org/web/20170202003812/http://www.dms.umontreal.ca/~andrew/PDF/BinCoeff.pdf
- 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）收敛点上的迭代器。
The parameter should be in either of the following to forms: - A list of partial quotients, possibly with the last element being a list of repeating partial quotients, such as might be returned by continued_fraction and continued_fraction_periodic. - An iterable returning successive partial quotients of the continued fraction, such as might be returned by continued_fraction_iterator.
In computing the convergents, the continued fraction need not be strictly in canonical form (all integers, all but the first positive). Rational and negative elements may be present in the expansion.
实例
>>> 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的连分式展开。
实例
>>> 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) list[源代码]#
求二次无理数的周期连分式展开式。
计算有理数或二次无理数的连分式展开，即。 \(\frac{{p + s\sqrt{{d}}}}{{q}}\) 在哪里 \(p\) ， \(q \ne 0\) 和 \(d \ge 0\) 是整数。
以整数列表的形式返回连分式表示（规范形式），可以选择以表示重复数字的整数列表结尾（对于二次非有理数）。
- 参数:
p ：内景
数分子的有理部分
q ：内景
数的分母
d ：int，可选
数字分子的无理部分（鉴别器）
s ：int，可选
无理部分系数
实例
>>> 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]
工具书类
[R712]K、 罗森。初等数论及其应用。Addison Wesley，3分版，第379-381页，1992年1月。
- 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)[源代码]#
返回其键为
n在给定的基础上，b，键表示数字中出现的数字，值表示该数字出现的次数。实例
>>> from sympy.ntheory import count_digits
>>> count_digits(1111339) {1: 4, 3: 2, 9: 1}
返回的数字总是以10为基数表示，但数字本身可以Python理解的任何格式输入；如果数字与10不同，也可以给出基数：
>>> n = 0xFA; n 250 >>> count_digits(_) {0: 1, 2: 1, 5: 1} >>> count_digits(n, 16) {10: 1, 15: 1}
对于数字中没有出现的任何数字，默认字典都将返回0。例如，哪些数字在
77!：>>> 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（或）-b如果n是否定的）。- 参数:
n： 整数
返回其位数的数字。
b： 整数
计算位数的基数。
位数：整数（或所有位数均为无）
要返回的位数（如有必要，用零填充）。
实例
>>> 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)[源代码]#
返回True如果
n在给定的基址上从左到右或从右到左读都是一样的，b.实例
>>> from sympy.ntheory import is_palindromic
>>> all(is_palindromic(i) for i in (-11, 1, 22, 121)) True
第二个参数允许您测试其他基数的数字。例如，88在base10中是回文，而在base-8中不是：
>>> is_palindromic(88, 8) False
另一方面，一个数可以是以8为基数的回文，而不是以10为基数的：
>>> 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')[源代码]#
Return the list of denominators of an Egyptian fraction expansion [R713] of the said rational \(r\).
- 参数:
r : Rational or (p, q)
a positive rational number,
p/q.algorithm : { "Greedy", "Graham Jewett", "Takenouchi", "Golomb" }, optional
表示要使用的算法（默认为“贪婪”）。
实例
>>> 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]
笔记
目前支持以下算法：
贪婪算法
Also called the Fibonacci-Sylvester algorithm [R714]. At each step, extract the largest unit fraction less than the target and replace the target with the remainder.
它有一些独特的特性：
鉴于 \(p/q\) 在最低条件下，生成最大长度的扩展 \(p\) . 即使分子越来越大，术语的数量也很少超过少数。
使用最小内存。
这些术语可能会爆炸（标准的例子是5/121和31/311）。分母在每一步最多为平方（双指数增长），通常表现为单指数增长。
格雷厄姆-杰维特算法
The algorithm suggested by the result of Graham and Jewett. Note that this has a tendency to blow up: the length of the resulting expansion is always
2**(x/gcd(x, y)) - 1. See [R715].Takenouchi算法
The algorithm suggested by Takenouchi (1921). Differs from the Graham-Jewett algorithm only in the handling of duplicates. See [R715].
Golomb算法
A method given by Golumb (1962), using modular arithmetic and inverses. It yields the same results as a method using continued fractions proposed by Bleicher (1972). See [R716].
在给定有理数大于或等于1的情况下，给出了求谐波序列1/1+1/2+1/3+求和的贪婪算法。。。，取此序列的所有单位分数，直到再加一个将大于给定的数字。这个分母列表是在对余数使用的请求算法的结果前面加上前缀的。例如，如果我们得到的是贪婪算法 [1、2、3、4、5、6、7、14、420] ，其中序列的开头， [1、2、3、4、5、6、7] 是谐波序列的一部分，求和为363/140，余数为31/420，即 [14420年] 通过贪婪算法。埃及_分数（有理（8，3），“Golomb”）的结果是 [1、2、3、4、5、6、7、14、574、2788、6460、11590、33062、113820] 等等。
工具书类
- sympy.ntheory.bbp_pi.pi_hex_digits(n, prec=14)[源代码]#
返回一个包含
prec（默认为14）以十六进制表示的从pi的第n位开始的数字。数字的计数从0开始，小数点不计数，因此对于n=0，返回值从3开始；n=1对应于小数点后的第一个数字（十六进制为2）。- 参数:
n : non-negative integer
prec : non-negative integer. default = 14
- 返回:
str : Returns a string containing
precdigitsstarting at the nth digit of pi in hex. If
prec= 0, returns empty string.- 加薪:
ValueError
If
n< 0 orprec< 0. Ornorprecis not an integer.
实例
>>> from sympy.ntheory.bbp_pi import pi_hex_digits >>> pi_hex_digits(0) '3243f6a8885a30' >>> pi_hex_digits(0, 3) '324'
These are consistent with the following results
>>> import math >>> hex(int(math.pi * 2**((14-1)*4))) '0x3243f6a8885a30' >>> hex(int(math.pi * 2**((3-1)*4))) '0x324'
工具书类
ECM function#
The \(ecm\) function is a subexponential factoring algorithm capable of factoring numbers of around ~35 digits comfortably within few seconds. The time complexity of \(ecm\) is dependent on the smallest proper factor of the number. So even if the number is really large but its factors are comparatively smaller then \(ecm\) can easily factor them. For example we take \(N\) with 15 digit factors \(15154262241479\), \(15423094826093\), \(799333555511111\), \(809709509409109\), \(888888877777777\), \(914148152112161\). Now N is a 87 digit number. \(ECM\) takes under around 47s to factorise this.
- sympy.ntheory.ecm.ecm(n, B1=10000, B2=100000, max_curve=200, seed=1234)[源代码]#
Performs factorization using Lenstra's Elliptic curve method.
This function repeatedly calls
_ecm_one_factorto compute the factors of n. First all the small factors are taken out using trial division. Then_ecm_one_factoris used to compute one factor at a time.- 参数:
n : Number to be Factored
B1 : Stage 1 Bound. Must be an even number.
B2 : Stage 2 Bound. Must be an even number.
max_curve : Maximum number of curves generated
seed : Initialize pseudorandom generator
实例
>>> 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 function#
The \(qs\) function is a subexponential factoring algorithm, the fastest factoring algorithm for numbers within 100 digits. The time complexity of \(qs\) is dependent on the size of the number so it is used if the number contains large factors. Due to this while factoring numbers first \(ecm\) is used to get smaller factors of around ~15 digits then \(qs\) is used to get larger factors.
For factoring \(2709077133180915240135586837960864768806330782747\) which is a semi-prime number with two 25 digit factors. \(qs\) is able to factorize this in around 248s.
- sympy.ntheory.qs.qs(N, prime_bound, M, ERROR_TERM=25, seed=1234)[源代码]#
Performs factorization using Self-Initializing Quadratic Sieve. In SIQS, let N be a number to be factored, and this N should not be a perfect power. If we find two integers such that
X**2 = Y**2 modNandX != +-Y modN, then \(gcd(X + Y, N)\) will reveal a proper factor of N. In order to find these integers X and Y we try to find relations of form t**2 = u modN where u is a product of small primes. If we have enough of these relations then we can form(t1*t2...ti)**2 = u1*u2...ui modNsuch that the right hand side is a square, thus we found a relation ofX**2 = Y**2 modN.Here, several optimizations are done like using multiple polynomials for sieving, fast changing between polynomials and using partial relations. The use of partial relations can speeds up the factoring by 2 times.
- 参数:
N : Number to be Factored
prime_bound : upper bound for primes in the factor base
M : Sieve Interval
ERROR_TERM : Error term for checking smoothness
threshold : Extra smooth relations for factorization
seed : generate pseudo prime numbers
实例
>>> 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}