Let's say I have generated 16 integers (between 0 and 128) using Python
from random import seed, randint
seed(1234)
randoms = [randint(0, 128) for _ in range(0, 16)]
If we have a rough knowledge of the seed (its number of digits for example), is it physically possible to retrieve the seed of the random generation with only those 16 numbers? If so, how much time would it take with an average computer?
First note that the random generator in Python is explicitly documented as "completely unsuitable for cryptographic purposes".
It is also documented that it uses "the Mersenne Twister as the core generator. It produces 53-bit precision floats and has a period of 2**19937-1.". From this question it looks like that Python uses MT19937, which is known to be predictable when observing 624 iterations, see als Wikipedia about it. There are also programs like this which show how you get the state and predict the next numbers if 624 values are observed.
It is not possible to determine the state from only 16 numbers though, i.e. there would be multiple possible states for this. Knowing the number of digits in the seed would not add sufficient information either.
Since this specific random generator is declared unsuitable for cryptography I recommend to check math.stackexchange.com if you want to get more into the details of this algorithm.
It depends on the PRNG (Psuedo-Random number generator) at play. Couldn't immediately find what is used at the heart of Python.
PRNG is just a bit of math on a (hopefully) unpredictable value often chained forward to produce new random numbers on each subsequent call. There have been many PRNG algorithms, a few we know how to reverse.
The only algorithms where the seed (should) be unrecoverable are CSPRNG (Cryptographically Secure PRNG). These roughly take the seed and encrypt/permute it with an irreversible (without knowledge of the key) cryptographic operation (AES, Chacha, etc). Unless the underlying cryptographic alogrithm is broken, it is assumed the seed cannot be found.
See the links below for some interesting reading on how the seed of javascript's Math.random() 'random' number generator can be cracked, with just a few samples:
Predicting Math.random() numbers?
Why is Math.random() not designed to be cryptographically secure?
