Algorithm for detecting parity of integers
A fundamentally linear model like logistic regression will never work well, because its assumptions are not at all true for your data set. It presumes that probability (OK, really, log odds) of being positive or negative changes linearly in each input, but, it alternates with each integer value in your input. KNN's assumption likewise does not match. For each integer, its neighbors have an opposite classification. These will never work well as applied to your input, because your input doesn't match their usage.

If however you include the parity of the input (X mod 2) as a feature, they should all trivially learn this model.

This is a pretty good simple lesson in feature engineering and understanding the assumptions you take on when applying an algorithm.