Verify the bounded discrepancy of an input sequence: Difference between revisions
From Polymath Wiki
Jump to navigationJump to search
Yangofzeal (talk | contribs) New page: <pre> #!/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: +... |
Yangofzeal (talk | contribs) No edit summary |
||
(2 intermediate revisions by the same user not shown) | |||
Line 1: | Line 1: | ||
[http://michaelnielsen.org/polymath1/index.php?title=Experimental_results back to the main experimental results page]. | |||
<pre> | <pre> | ||
#!/usr/bin/env python | #!/usr/bin/env python | ||
Line 14: | Line 16: | ||
from __future__ import with_statement | from __future__ import with_statement | ||
from numpy import zeros, int8 | from numpy import zeros, int8 | ||
SEQUENCE_LENGTH = 1124 | |||
fileInput = '1124_min.txt' | fileInput = '1124_min.txt' | ||
Line 20: | Line 22: | ||
pass | pass | ||
def verifySequence(x, | def verifySequence(x, C=2, verbose=False): | ||
"""verify discrepancy <= | """verify discrepancy <= C | ||
""" | """ | ||
for i in range( | for i in range(SEQUENCE_LENGTH): | ||
inds = range(i, | inds = range(i,SEQUENCE_LENGTH,i+1) | ||
s = x[inds].sum() # discrepancy | s = x[inds].sum() # discrepancy | ||
if abs(s) > | if abs(s) > C: | ||
msg = ' | msg = 'd = %d has discrepancy %s' | ||
msg %= (i+1, s) | msg %= (i+1, s) | ||
raise DiscrepancyError(msg) | raise DiscrepancyError(msg) | ||
Line 37: | Line 39: | ||
if __name__=='__main__': | if __name__=='__main__': | ||
# load +/- sequence | # load +/- sequence | ||
x = zeros( | x = zeros(SEQUENCE_LENGTH, dtype = int8) | ||
with open(fileInput, 'r') as f: | with open(fileInput, 'r') as f: | ||
a = f.read() | a = f.read() | ||
Line 45: | Line 47: | ||
elif side == '+': | elif side == '+': | ||
x[i] = 1 | x[i] = 1 | ||
assert i == | assert i == SEQUENCE_LENGTH - 1 | ||
isGood = verifySequence(x) | isGood = verifySequence(x) | ||
</pre> | </pre> |
Latest revision as of 18:43, 11 January 2010
back to the main experimental results page.
#!/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 SEQUENCE_LENGTH = 1124 fileInput = '1124_min.txt' class DiscrepancyError(Exception): pass def verifySequence(x, C=2, verbose=False): """verify discrepancy <= C """ for i in range(SEQUENCE_LENGTH): inds = range(i,SEQUENCE_LENGTH,i+1) s = x[inds].sum() # discrepancy if abs(s) > C: msg = 'd = %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(SEQUENCE_LENGTH, 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 == SEQUENCE_LENGTH - 1 isGood = verifySequence(x)