Verify the bounded discrepancy of an input sequence
From Polymath Wiki
#!/usr/bin/env python
"""Erdos Discrepancy Problem sequence verification.
Verifies that discrepancy is bounded
for 1124-length sequence of +/-1.
file 1124_min.txt should contain:
+ - + + - - - - ...
by Michael Yang, 2010
"""
from __future__ import with_statement
from numpy import zeros, int8
N = 1124
fileInput = '1124_min.txt'
class DiscrepancyError(Exception):
pass
def verifySequence(x, maxDiscrepancy=2, verbose=False):
"""verify discrepancy <= MAX_DISCREPANCY
"""
for i in range(N):
inds = range(i,N,i+1)
s = x[inds].sum() # discrepancy
if abs(s) > maxDiscrepancy:
msg = 'n = %d has discrepancy %s'
msg %= (i+1, s)
raise DiscrepancyError(msg)
if verbose: print i+1, s
if verbose: print 'verified'
return True
if __name__=='__main__':
# load +/- sequence
x = zeros(N, dtype = int8)
with open(fileInput, 'r') as f:
a = f.read()
for i, side in enumerate(a.strip().split()):
if side == '-':
x[i] = -1
elif side == '+':
x[i] = 1
assert i == N - 1
isGood = verifySequence(x)