rendered paste body# Sorry for the ugly code.def seqoutcomes(N, prevoutcomes=None): if N == 0: return {0: frozenset([None])} outcomes = {} prevoutcomes = prevoutcomes or seqoutcomes(N - 1) def addoutcomes(spec, o): outcomes.setdefault(o, set()).add(spec) for outcome, specs in prevoutcomes.iteritems(): addoutcomes((specs, getsize(specs), 1), outcome + N * N) addoutcomes((specs, getsize(specs), -1), outcome - N * N) #print ', '.join('%d sum up to %d' % (len(specs), o) for (o, specs) in outcomes.iteritems()) return dict((o, frozenset(specs)) for (o, specs) in outcomes.iteritems())def getsize(specs): size = 0 for spec in specs: if spec == None: size += 1 else: size += spec[1] return sizedef outcomeseqs(specs): for spec in specs: if spec == None: yield [] else: for suboutcomeseq in outcomeseqs(spec[0]): yield suboutcomeseq + [spec[2]]def outcomestring(seq, outcome): return '%d == %s' % (outcome, ' '.join( '%s %d^2' % ('+' if sign > 0 else '-', i + 1) for (i, sign) in enumerate(seq)))def printoutcomenumbers(to=100): last = None for N in range(1, to): last = seqoutcomes(N, last) print "N = %d: " % N, if 0 in last: print "%d combinations, e.g. %s" % (getsize(last[0]), outcomestring(outcomeseqs(last[0]).next(), 0)) else: print "impossible"# >>> printoutcomenumbers()# N = 1: impossible# N = 2: impossible# N = 3: impossible# N = 4: impossible# N = 5: impossible# N = 6: impossible# N = 7: 2 combinations, e.g. 0 == - 1^2 - 2^2 + 3^2 - 4^2 + 5^2 + 6^2 - 7^2# N = 8: 2 combinations, e.g. 0 == + 1^2 - 2^2 - 3^2 + 4^2 - 5^2 + 6^2 + 7^2 - 8^2# N = 9: impossible# N = 10: impossible# N = 11: 2 combinations, e.g. 0 == + 1^2 - 2^2 + 3^2 + 4^2 + 5^2 - 6^2 - 7^2 - 8^2 + 9^2 - 10^2 + 11^2# N = 12: 10 combinations, e.g. 0 == + 1^2 + 2^2 + 3^2 + 4^2 + 5^2 - 6^2 + 7^2 - 8^2 - 9^2 + 10^2 + 11^2 - 12^2# N = 13: impossible# N = 14: impossible# N = 15: 86 combinations, e.g. 0 == - 1^2 - 2^2 - 3^2 - 4^2 - 5^2 + 6^2 + 7^2 + 8^2 + 9^2 + 10^2 + 11^2 - 12^2 + 13^2 - 14^2 - 15^2# N = 16: 114 combinations, e.g. 0 == - 1^2 - 2^2 - 3^2 + 4^2 + 5^2 + 6^2 + 7^2 + 8^2 + 9^2 + 10^2 + 11^2 - 12^2 - 13^2 - 14^2 - 15^2 + 16^2# N = 17: impossible# N = 18: impossible# N = 19: 478 combinations, e.g. 0 == - 1^2 - 2^2 + 3^2 + 4^2 + 5^2 + 6^2 + 7^2 + 8^2 + 9^2 + 10^2 + 11^2 + 12^2 + 13^2 + 14^2 + 15^2 - 16^2 - 17^2 - 18^2 - 19^2# N = 20: 860 combinations, e.g. 0 == - 1^2 - 2^2 + 3^2 + 4^2 - 5^2 + 6^2 - 7^2 - 8^2 - 9^2 - 10^2 - 11^2 - 12^2 - 13^2 - 14^2 - 15^2 - 16^2 + 17^2 + 18^2 + 19^2 + 20^2# N = 21: impossible# N = 22: impossible# N = 23: 5808 combinations, e.g. 0 == + 1^2 - 2^2 + 3^2 + 4^2 - 5^2 - 6^2 + 7^2 - 8^2 - 9^2 + 10^2 - 11^2 - 12^2 - 13^2 - 14^2 - 15^2 - 16^2 + 17^2 + 18^2 + 19^2 - 20^2 - 21^2 + 22^2 + 23^2# N = 24: 10838 combinations, e.g. 0 == + 1^2 + 2^2 + 3^2 + 4^2 + 5^2 - 6^2 - 7^2 - 8^2 - 9^2 - 10^2 + 11^2 - 12^2 - 13^2 - 14^2 - 15^2 - 16^2 - 17^2 + 18^2 + 19^2 - 20^2 - 21^2 + 22^2 + 23^2 + 24^2# N = 25: impossible# N = 26: impossible# N = 27: 55626 combinations, e.g. 0 == - 1^2 + 2^2 - 3^2 - 4^2 - 5^2 + 6^2 + 7^2 + 8^2 + 9^2 + 10^2 + 11^2 + 12^2 - 13^2 + 14^2 + 15^2 + 16^2 - 17^2 - 18^2 - 19^2 + 20^2 - 21^2 + 22^2 - 23^2 + 24^2 - 25^2 - 26^2 + 27^2# N = 28: 100426 combinations, e.g. 0 == + 1^2 + 2^2 + 3^2 - 4^2 + 5^2 + 6^2 + 7^2 - 8^2 + 9^2 + 10^2 - 11^2 + 12^2 + 13^2 + 14^2 + 15^2 + 16^2 - 17^2 + 18^2 + 19^2 - 20^2 - 21^2 - 22^2 - 23^2 + 24^2 + 25^2 + 26^2 - 27^2 - 28^2# N = 29: impossible# N = 30: impossible# N = 31: 696164 combinations, e.g. 0 == - 1^2 - 2^2 + 3^2 + 4^2 - 5^2 + 6^2 + 7^2 + 8^2 + 9^2 + 10^2 + 11^2 + 12^2 + 13^2 - 14^2 + 15^2 + 16^2 + 17^2 - 18^2 - 19^2 + 20^2 - 21^2 + 22^2 - 23^2 + 24^2 - 25^2 + 26^2 + 27^2 + 28^2 - 29^2 - 30^2 - 31^2# N = 32: 1298600 combinations, e.g. 0 == + 1^2 - 2^2 + 3^2 + 4^2 + 5^2 + 6^2 + 7^2 - 8^2 + 9^2 + 10^2 + 11^2 + 12^2 + 13^2 + 14^2 + 15^2 + 16^2 + 17^2 + 18^2 - 19^2 + 20^2 + 21^2 + 22^2 - 23^2 - 24^2 - 25^2 - 26^2 + 27^2 + 28^2 + 29^2 - 30^2 - 31^2 - 32^2# N = 33: impossible# N = 34: impossible# N = 35: 7826992 combinations, e.g. 0 == - 1^2 - 2^2 + 3^2 - 4^2 + 5^2 - 6^2 + 7^2 - 8^2 - 9^2 - 10^2 - 11^2 - 12^2 - 13^2 + 14^2 - 15^2 - 16^2 - 17^2 - 18^2 - 19^2 - 20^2 - 21^2 - 22^2 + 23^2 - 24^2 - 25^2 + 26^2 - 27^2 - 28^2 + 29^2 + 30^2 + 31^2 + 32^2 + 33^2 + 34^2 - 35^2# N = 36: 14574366 combinations, e.g. 0 == - 1^2 - 2^2 - 3^2 + 4^2 - 5^2 + 6^2 - 7^2 + 8^2 + 9^2 + 10^2 + 11^2 + 12^2 + 13^2 - 14^2 - 15^2 - 16^2 + 17^2 - 18^2 - 19^2 - 20^2 - 21^2 + 22^2 + 23^2 + 24^2 + 25^2 + 26^2 - 27^2 - 28^2 + 29^2 + 30^2 - 31^2 - 32^2 - 33^2 + 34^2 - 35^2 + 36^2# N = 37: impossible# N = 38: impossible