Cursed, coinductive and tail-recursive implementation of `is_odd`. Time complexity is O(n) when n is odd ; otherwise, it does not terminate (up to the machine's physical limits).

is_odd_cursed.py

# ruff: noqa: S101, PLR6301, RUF002
"""
Cursed implementation of `is_odd`.

It relies on two interesting properties. Firstly, the set formed
by the difference of consecutive squares is the odd members of
ℕ - let's call this set ℕ_odd.
Secondly, the negative integers are symmetric to their positive
counterparts with respect to oddness. Differently put, negating
a number preserves the fact that it is odd.
Combining these gives us the ability to check if an integer is
odd by verifying if it is a member of ℕ_odd.
"""

from __future__ import annotations

import unittest


def next_square(n: int) -> int:
    """
    Return (n + 1)².
    """

    if n == -1:
        return 0

    if n < -1:
        # the next square of a negative integer is the previous
        # one when its sign gets flipped!
        return next_square(-n - 2)

    # (n + 1)² = n² + 2n + 1
    return next_square(n - 1) + n + n + 1


def is_odd(n: int) -> bool:
    """
    Return whether `n` is odd.
    """

    if n < 0:
        return is_odd(-n)

    if n == 0:
        return False  # 0 is considered even here

    def tail_recursive(n: int, current: int = 0) -> bool:
        """
        Coinductive¹, tail-recursive function that checks
        whether n is odd or not.

        ¹ Yes, it is coinductive. The parameter on which it is
        iterating over is structurally increasing.
        """

        if n == next_square(current) - next_square(current - 1):
            return True

        return tail_recursive(n, current + 1)

    return tail_recursive(n)


class TestIsOdd(unittest.TestCase):
    """
    Test class for the `is_odd` function.
    """

    def test_zero(self) -> None:
        """
        Test for the case where the argument is 0.
        """

        assert not is_odd(0)

    def test_odd_int(self) -> None:
        """
        Test for the case where the integer argument is indeed odd.
        """

        assert is_odd(5)

    # We cannot test even numbers, as the function would not terminate


if __name__ == "__main__":
    _ = unittest.main()