Skip to content

Instantly share code, notes, and snippets.

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