Who never dreamed of predicting the winning sequence in a Casino slot machine ? The goal of this puzzle is to predict the next value from a realistic pseudo random sequence of numbers. Obviously one couldn't stay in front of a slot machine for too long without attracting suspicion, so we will assume that you stay a little while in front of it to observe a sequence, then move away and come back to observe more. Consequently for each test case you are presented with a list of observed sequences and the formula to compute the next value from the current value.
The formula is based on simple boolean shift, and, or and xor operations:
sj+1 = (sj>>1) | (^(sj & f) << (b-1))
- sj+1 is the j+1th value in the sequence s
- sj is the jth value in the sequence s
- f is the function vector (unknown to you)
- b is the number of bits (unknown to you)
- ^ represents the xor bit reduction:
- ^v = 1 if the number of 1 in v is odd (example: ^1011 = 1)
- ^v = 0 if the number of 1 in v is even (example: ^0101 = 0)
Note that this formula is actually used in many modern digital systems, such as TV broadcasting, GPS signals, Linux, etc... For more information, read this Wikipedia article.