Skip to content

Instantly share code, notes, and snippets.

# richardkiss/f(f(n)) = -n.py Created Jun 28, 2013

 #!/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()
to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.