# Difference between revisions of "Verify the bounded discrepancy of an input sequence"

From Polymath Wiki

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) m (Changed variable names to be more in harmony with theory page) |
||

Line 14: | Line 14: | ||

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 20: | ||

pass | pass | ||

− | def verifySequence(x, | + | def verifySequence(x, C=2, verbose=False): |

− | """verify discrepancy <= | + | """verify discrepancy <= MAX_DISCREPASEQUENCE_LENGTHCY |

""" | """ | ||

− | 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 37: | ||

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 45: | ||

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> |

## Revision as of 01:29, 12 January 2010

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