Rational Recurrence Relation

The following is a function defined for all positive rational values of $x$.

$$ f(x)=\begin{cases} x &x\text{ is integral}\\
f(\frac 1{1-x}) &x \lt 1\\
f\Big(\frac 1{\lceil x\rceil -x}-1+f(x-1)\Big) &\text{otherwise}\end{cases} $$

For example, $f(3/2)=3$, $f(1/6) = 65533$ and $f(13/10) = 7625597484985$.

Find $f(22/7)$. Give your answer modulo $10^{15}$.

The function f given in question statement is called the Collatz function, a variation of the famous Collatz Conjecture. This problem basically requires us to recursively apply the rules given until we get an integer, then return the integer.

For $f(22/7)$, we’re starting off with a noninteger. Since 22/7 is greater than 1, we apply the third branch of the function:

$f(22/7)=f\Big(\frac{1}{\lceil 22/7 \rceil -22/7}-1+f(22/7-1)\Big)$

Simplified this looks like:
$f(22/7)=f\Big(\frac{1}{3 – 22/7}-1+f(1/7)\Big)$

The ceiling function $\lceil x \rceil$ here stands for the smallest integer that is greater than or equal to x. For $22/7$, $3$ is the smallest integer that is greater than $22/7$ since $22/7$ is clearly less than $3$ but greater than $2$.

Simplifying the inside of the function gives:
$f(22/7)=f(f(1/7)+146/49)$

The recursion continues by applying the third case to $f(146/49)$ until we get an integer. Care should be taken in this process, and it should be noted that in such recurrence relations, the process might take a long time or even not terminate.

For some specific values this process might be too long to practically compute or the recursion may not even terminate. To find out whether $f(22/7)$ terminates and what its value would be, consider using a computer program to iteratively apply the function rules and check for termination.

Given that the values for $f(3/2)$, $f(1/6)$ and $f(13/10)$ are known and relatively small, it is reasonable to expect that the value for $f(22/7)$ may terminate and not be exceedingly large. However, answering this problem definitely would require more extensive computation beyond paper and pencil work.

Also, please note that the question requires the answer modulo $10^{15}$. The modulo operator in mathematics is the remainder when dividing by a number. This means you are required to find the remainder when your answer is divided by $10^{15}$.

More Answers: