We often use Random number generators in our life. Java programming language has class java.util.Random for it. 64-bit parameter seed is maintained during the lifetime of an instance of this class. On creation it is initialized with random 48-bit value. Method nextInt(n) returns integer in range . On every call of nextInt(n) seed is changed and then number consisting of bits from 17 to 47 of seed, inclusive, is returned:

int nextInt(int n) {
	seed = (seed * 0x5DEECE66D + 0xB) & ((1L << 48) - 1);
	return (int) ((seed >>> 17) % n);
}

Note that in Java on overflow computations are done modulo .

Operator >>> in Java is zero fill right shift, it fills leading bits with zeros, even if number is negative. The behavior would be the same, if the variable were unsigned. (It exists, because Java doesn't have unsigned integer types)

Given ten output values of nextInt(1000), guess the next values to be output by the generator.