Author Dennis Sweeney
Recipients Dennis Sweeney, christian.heimes, jfine2358, mark.dickinson, remi.lapeyre, rhettinger, serhiy.storchaka, steven.daprano, tim.peters, trrhodes
Date 2020-05-06.20:25:00
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1588796701.24.0.922205195441.issue40028@roundup.psfhosted.org>
In-reply-to
Content
For some more ideas for features or APIs, you could look at: https://docs.sympy.org/latest/modules/ntheory.html or http://doc.sagemath.org/html/en/reference/rings_standard/sage/arith/misc.html for an absolute upper bound.

If there's to be a minimal number theory (imath?) module, I would interested in what's below. I'm a math student so perhaps my workload is perhaps not representative of most people (and I can turn to tools like SageMath for most of this), but nonetheless here would be my wishlist for the stdlib.

- prime_factors(n): iterator or tuple of prime factors in multiplicity
- factorization(n): like collections.Counter(prime_factors(n))
- divisors(n): iterator for divisors based on factorization
- is_prime(n, bases=20): do some randomized Miller-Rabin
- crt(moduli, values): Chinese Remainder Theorem
- xgcd(numbers) -> tuple[int, tuple[int]]: use the extended euclidean algorithm to find gcd and Bezout coefficients
- generate_primes(start=2)
- next_prime(n) / prev_prime(n)
- prime_range(a, b)
- is_square(n) (maybe is_nth_power?)
- multiplicity(p, n): maximal r such that p**r divides n
- is_quadratic_residue(a, modulus)
- primitive_root(modulus)
- multinomial(n, *ks)

Already in math module:
- gcd and lcm 
- comb(n, k)
- perm(n, k)
- isqrt(n)
- factorial(n)

Looking at this list though, I realize that there is infinite potential for feature-creep, and so it would be nice to have an explicit set of guidelines for what sorts of functions are allowed. Perhaps something like "must have a common-enough use case outside of pure math". There's also a limitless amount of micro-optimization that can come with several of these (is_prime, is_square, generate_primes, etc.), so it might be nice to have a guideline about only accepting performace optimizations if the cost in complexity is small.
History
Date User Action Args
2020-05-06 20:25:01Dennis Sweeneysetrecipients: + Dennis Sweeney, tim.peters, rhettinger, mark.dickinson, christian.heimes, steven.daprano, serhiy.storchaka, remi.lapeyre, jfine2358, trrhodes
2020-05-06 20:25:01Dennis Sweeneysetmessageid: <1588796701.24.0.922205195441.issue40028@roundup.psfhosted.org>
2020-05-06 20:25:01Dennis Sweeneylinkissue40028 messages
2020-05-06 20:25:00Dennis Sweeneycreate