Maybe this is a problem we could use ethereum smart contracts to solve. Actually, is flipping a number even in P? Verification is easy - just compare against the negative - but I'm not sure if flipping the number can be done in polynomial time, enumerating all cases (as OP has done) aside.