Verify the bounded discrepancy of sequence
From Polymath Wiki
Jump to navigationJump to search
#!/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)