Find function of which the return set is the intersection of the return sets of two other functions-CodePudding

Consider a function which takes any integer, and returns something, of which the nature may be whatever. I call the set of values such a function can return, its return set.

I want a way to produce a new such function, from two of such functions, of which the return set is the intersection of the return sets of the two already existing functions.

Let me give an example. Let's say the two functions are

int DivisibleByTwo(int i)
{
    return 2 * i;
}

int DivisibleByThree(int i)
{
    return 3 * i;
}

The return set of the first function is obviously all integers that are divisible by two, and the return set of the second is obviously all integers that are divisible by three (assuming we don't have to worry about things like max integer sizes). The return set of the function i want to find, is of course then all integers which are divisible both by two and three. A possible way to implement this is

int DivisibleByTwoAndThree(int i)
{
    return 2 * 3 * i;
}

Now i could find that function easily in my head. But what i want, is a program that does this automatically. And that's where im stuck, i can't seem to come up with an algorithm that does this, it feels more or less impossible. So i am asking, am i dealing with something actually impossible? And if no, how would i approach it?

CodePudding user response：

Here is a Python solution for non-negative integers. Its efficiency is..terrible. In fact if the intersection of the two outputs is finite, it can run forever without returning an answer. Ditto if either input function gets stuck.

def natural_pairs ():
    yield (0, 0)
    i = 0
    while True:
        i = i   1
        j = 0
        while j <= i:
            yield (i, j)
            yield (j, i)
            j = j 1

def intersect_functions (f, g):
    def intersected (n):
        for i, j in natural_pairs():
            if f(i) == g(j):
                n -= 1
                if n < 0:
                    return f(i)

    return intersected


def times2 (n):
    return 2*n

def times3(n):
    return 3*n


combined = intersect_functions(times2, times3)

for i in range(10):
    print(i, combined(i))

I believe that Cantor would be proud.