]Serhiy Storchaka <storchaka@gmail.com>]

I have mixed feelings :-(  There are a number of integer functions broadly useful to people attracted to such things, and "it would be nice" to have basic implementations ship with the language.

But the "basic" is important to me.  Algorithms for unbounded integers can grow in complexity seemingly without bound too, and by the time there are 10 special cases 8 of which have been coded in C, it becomes an ongoing maintenance headache - and the code has become so complex that users can't easily look at the source to judge whether the implementation is _still_ too naive for their application.

For example, for generating primes, I'd balk at anything fancier than my recoding in Python 3 of Will Ness's beautiful algorithm:

    https://stackoverflow.com/a/19391111/2705542

That generates primes in increasing order, with no need (or even possibility) to specify an upper bound in advance.  But unlike nearly all other reasonably efficient approaches to that, the memory burden grows (very roughly) with the square root of the largest prime generated so far.  Most sieve algorithms require instead remembering all the ~P/log(P) primes <= P, which grows much faster than sqrt(P).  That's a real practical difference.

There are faster ways to generate the primes, and even that way can be sped significantly by complicating the code significantly to incorporate a multiple-small-prime wheel.

But I'd much rather leave significantly more complicated code to _specialized_, non-core packages.

Anyway, in addition to your list, there are at least four others I view as fundamental:

def iroot(n, k):  # the obvious generalization of integer square root

    """Return the floor of the k'th root of n."""

def factor(n):

    """Return a list containing n's prime factors."""

State-of-the-art code for `factor()` alone could double the size of the Python source distribution ;-)