# Union and intersection of recursive sets

I want a function that can find the $$n$$-th element of the union of two recursive sets. The dumb way is to test every natural number, and see if it belongs to either set. A much better method is to keep an index into each set. Each index starts by pointing at the first element of each set. We always increment the index which points to the smallest value. If they point to equal values, then both indices shall be incremented.

def union(f, g, x):
i = 0
j = 0
while 1:
if f(i) < g(j):
if x == 0:
return f(i)
x -= 1
i += 1
elif g(j) < f(i):
if x == 0:
return g(j)
x -= 1
j += 1
else:
if x == 0:
return f(i)
i += 1
j += 1


Now that we have the union, let's do the same for intersection:


def inter(f, g, x):
i = 0
j = 0
while 1:
if f(i) < g(j):
i += 1
elif g(j) < f(i):
j += 1
else:
if x == 0:
return f(i)
x -= 1
i += 1
j += 1



def f(x):
return 2*x

def g(x):
return 3*x + 1

n = 30
for i in range(0, n):
print(union(f, g, i), end = '')
if i < n - 1:
print(', ', end = '')
print('\n')
for i in range(0, n):
print(inter(f, g, i), end = '')
if i < n - 1:
print(', ', end = '')
print()