Generate a (completely deterministic) pseudorandom bit stream
C, 61

main(s,n){for(n=1u&lt;&lt;31;putchar((s%=n)/(n/2)&amp;1|48);s*=65539);}


Yeah, I know it's not code golf. This is obviously rather an anti-solution... but it sure enough fulfills your criteria.


  $ ./a.out | head -c840
  000000001000111101100110110011100100011101110001101001101110011101100111010111010010001001110001111110010001010101101000110101000011110010100101001101110100011111000101000110000111100100010101010100110101101010001110101000011011001010111011110110101000001110011000010100001111110110001000000101100011000110000010110011000010101101011100010011011111111100001010111110111010110001000010110111000010101001000011001001110110001001101011011110111011010100000000001001010100111000000100010011110001010111001110101111100110110111010001101001100000101000111000101000110100001111010110100001100110011011110001011011100010111011100001110100110001010011001110001010110100111111111010110101100110000101111111111000111101100011000111010111010100110001001110101110100011101110001100110110000001100101110100101000101011100000110111101101100110000000101110
  $ ./a.out | head -c840 | perl tester.pl
  Test 2: 1 (1) 2.93333333333333 (3) 3.1 (3) 0.966666666666667 (1)
  Test 3:  214 99 71 24 7 5 1 1 2 2
  Test 4: 0.495238095238095


Period length is 2²⁹.