# Verify the bounded discrepancy of an input sequence

From Polymath1Wiki

Revision as of 17:29, 11 January 2010 by Yangofzeal (Talk | contribs)

#!/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 <= MAX_DISCREPASEQUENCE_LENGTHCY """ 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)