f(f(n)) = -n.py

#!/usr/bin/env python

"""
The obvious way is to do it with complex numbers.
"""

def f(x):
    # remember, in Python 1j means sqrt(-1)
    return 1j * x


"""
This is great, except f isn't closed under integers. But how about a clever remapping!

Let's define a function G that maps the integers into pure real and pure imaginary integers as follows:

-6 => -3
-5 => -3i
-4 => -2
-3 => -2i
-2 => -1
-1 => -i
 0 => 0
 1 => i
 2 => 1
 3 => 2i
 4 => 2
 5 => 3i
 6 => 3

This mapping is invertible; call the inverse H.

Note that G(-x) = -G(x) and H(-x) = -H(x). Eyeball the table to convince yourself.
"""

def G(n):
    # go from left to right
    if n % 2 == 0:
        # n is even
        return n//2
    # n is odd
    away_from_zero = abs(n)/n
    return 1j * ((n + away_from_zero)//2)

def H(c):
    # go from right to left
    a = c.real
    b = c.imag
    # c = a + bj
    # this only works for pure real or pure imaginary inputs
    assert a == 0 or b == 0
    if b == 0:
        # pure real
        return 2*a
    # pure imaginary
    towards_zero = -abs(b)/b
    return (2*b) + towards_zero

# great. Now we have three functions that use complex numbers instead of one. Clearly f(f(n)) = -n.
# But also H(G(n)) = n. So define F(x) = H(f(G(x)))
# Clearly F takes a real integer (same as G) and returns a real integer (same as H).
# F(F(x)) = H(f(G(H(f(G(x)))))) = H(f(f(G(x)))) (since H & G are inverses)
#         = H(-(G(x))) (since f(f(x)) = -x)
#         = -(H(G(x))) (since H(-x) = -H(x))
#         = -x
# So F satisfies this property too and only operates on integers!

def F(x):
    return H(f(G(x)))

# bully. We can actually refactor H, f and G into one big F function.

def F_composed(n):
    # the G part
    if n % 2 == 0:
        real = n//2
        imag = 0
    else:
        away_from_zero = abs(n)/n
        real = 0
        imag = ((n + away_from_zero)//2)

    # the f part (multiply by i)
    real, imag = -imag, real

    # the H part
    a = real
    b = imag
    # c = a + bj
    # this only works for pure real or pure imaginary inputs
    assert a == 0 or b == 0
    if b == 0:
        # pure real
        return 2*a
    # pure imaginary
    towards_zero = -abs(b)/b
    return (2*b) + towards_zero

# you can make this (way) more concise

def F_more_concise(n):
    if n == 0: return 0
    away_from_zero = abs(n)/n
    if n % 2 == 0:
        return n - away_from_zero
    return -(n + away_from_zero)

# Ta da

def test():
    for test_f in [F, F_composed, F_more_concise]:
        for n in range(-10, 11):
            print("f(%3d) = %3d; f(f(%3d)) = %3d" % (n, test_f(n), n, test_f(test_f(n))))
        print("-"*80)

test()