Computationally finding roots of a recursive function

Question

I'm having a pretty complex function $h(n,d) = f(n,d) -n$ where $n \in \mathbb{N}$ and $d \in [1,9] \subset \Bbb{R}$. $f(n,d)$ is recursively defined.

$$f(n, d) = \begin{cases} n<0\quad f(|n|,d) \\ n=0\quad 0\\ 0<n<10\quad 1\\ n≥10\quad x g(y, d) + f(x-1, d) y + f(n \mod x,d) \end{cases}$$

where $x = 10^{\lfloor \log_{10} n \rfloor}$ and $y = \lfloor \frac n x \rfloor$;

$$g(n,d) = \begin{cases} n = d\quad 1\\ n ≠ d\quad 0\end{cases}$$

I'm not sure if the definition is complete, however the scheme should stay this way. It's pretty obvious that $h(n,d)$ is highly computationally expensive, however I need to find all roots of the function for every $d$.

Most algorithms to find a root that I know only work for polynomial functions or are dead slow and recursive themselves. What is the best way to find all roots of this function for specific $d$'s?

Answer 1

Edit : I added (3),(4).

This is a partial answer.

This answer proves the followings :

(1) $n=0,1$ are the only roots of $f(n,d)-n=0$ for each of $d=2,3,\cdots, 8$.

(2) If $f(n,1)-n=0$ where $10^k\le n\lt 10^{k+1}$ and $k\ge 1\in\mathbb N$, then $$10^k\le n\le 10^k+3\cdot 10^{k-1}-1.$$

(3) If $n$ is the root of $f(n,9)-n=0$, then $n\lt 10^{91}$.

(4) If $n$ is the root of $f(n,d)-n=0$ where $d=1$ or $9$, then the right-most two digits of $n$ is either $$00,01,12,23,34,45,56,67,78,89.$$

---

For (1)(2) :

We can trivially see that $n=0,1$ are the roots of $f(n,d)-n=0$ for each of $d=1,2,\cdots, 9$.

First of all, for $n\ge 10, k\ge 2\in\mathbb N$ and $d\not=9$, $$f(10^k-1,d)=10f(10^{k-1}-1,d)\quad\Rightarrow\quad f(10^k-1,d)=10^{k-1}$$ This is true for $k\ge 1\in\mathbb N$.

From this, for $10^k\le n\lt 10^{k+1}$ where $k\ge 1$ and $d\not=9$, since $\lfloor \log_{10}n\rfloor=k$,

$$f(n,d)=10^{k}g\left(\left\lfloor\frac{n}{10^{k}}\right\rfloor,d\right)+10^{k-1}\left\lfloor\frac{n}{10^{k}}\right\rfloor+f(n\pmod{10^{k}},d)$$

Here, we can prove by induction that for $10^k\le n\lt 10^{k+1}$ where $k\ge 1$ and $d\not=9$, $$f(n,d)\le 2\cdot 10^k-1.$$

Proof :

For $k=1$, $f(n,d)\le\max(10^1\cdot 0+10^{1-1}\cdot 9+1,10^1\cdot 1+10^{1-1}\cdot 8+1)=19$.

Assuming that $f(n,d)\le 2\cdot 10^k-1$ for $10^k\le n\lt 10^{k+1}$ gives that for $10^{k+1}\le n\lt 10^{k+2}$, $$\begin{align}f(n,d)&\le\max(10^{k+1}\cdot 0+10^k\cdot 9+2\cdot 10^k-1,10^{k+1}\cdot 1+10^k\cdot 8+2\cdot 10^k-1)\\&=2\cdot 10^{k+1}-1\qquad\blacksquare\end{align}$$

So, for $10^k\le n=f(n,d)\le 2\cdot 10^k-1$ where $k\ge 1$ and $d\not=9$, $$f(n,d)=10^{k}g\left(1,d\right)+10^{k-1}+f(n\pmod{10^{k}},d)$$ Here, suppose that $2\le d\le 8$. Then, $$f(n,d)\le 10^{k}\cdot 0+10^{k-1}+2\cdot 10^{k-1}-1$$ However, there is no $n$ such that $$n=f(n,d)\le 3\cdot 10^{k-1}-1\lt 10^k\le n$$ This is a contradiction.

So, since we have to have $d=1$, $$f(n,1)=10^{k}+10^{k-1}+f(n\pmod{10^{k}},1)$$ Thus, we have $$10^k\le n=f(n,1)\le 10^k+10^{k-1}+2\cdot 10^{k-1}-1=10^k+3\cdot 10^{k-1}-1.$$

---

For (3) :

For $k\ge 2$, $$f(10^{k}-1, 9) =10^{k-1}+ 10f(10^{k-1}-1, 9)\quad\Rightarrow\quad f(10^k-1,9)=k\cdot 10^{k-1}$$

So, for $10^k\le n\lt 10^{k+1}$ where $k\ge 1$, $$f(n, 9) =10^{k} g\left(\left\lfloor \frac{n}{10^{k}} \right\rfloor, 9\right) + k\cdot 10^{k-1}\left\lfloor \frac{n}{10^{k}} \right\rfloor+ f(n \pmod{10^{k}},9)$$

Here, we can prove by induction that for $10^k\le n\lt 10^{k+1}$ where $k\ge 1$, $$f(n,9)\ge \frac{(9k-1)\cdot 10^k+1}{81}.$$

Proof :

For $k=1$, $f(n,d)\ge 10^1\cdot 0+1\cdot 10^{1-1}\cdot 1+0=1$.

Assuming that $f(n,9)\ge \frac{(9k-1)\cdot 10^k+1}{81}$ for $10^k\le n\lt 10^{k+1}$ gives that for $10^{k+1}\le n\lt 10^{k+2}$, $$f(n,9)\ge 10^{k+1}\cdot 0+(k+1)\cdot 10^{k}\cdot 1+\frac{(9k-1)\cdot 10^k+1}{81}=\frac{(9k+8)\cdot 10^{k+1}+1}{81}\qquad\blacksquare$$

Here note that $$n=f(n,d)\ge \frac{(9k-1)\cdot 10^k+1}{81}\gt 10^{k+1}\gt n$$ holds for $k\ge 91$.

Hence, for $k\ge 91$, we have a contradiction.

So, we have to have $k\le 90$, so $n\lt 10^{90+1}=10^{91}.$

---

For (4) :

Since $f(10^k-1,1)=10^{k-1}$ for $k\ge 1$, for $10^k\le n\lt 10^{k+1}$ where $k\ge 1$, $$f(n, 1) =10^{k} g\left(\left\lfloor \frac{n}{10^{k}} \right\rfloor, 1\right) + 10^{k-1}\left\lfloor \frac{n}{10^{k}} \right\rfloor+ f(n \pmod{10^{k}},1)$$

In the following, $d=1,9$. Let $n=\sum_{i=0}^{m}a_i\cdot 10^i$. Also, let $[N]$ be the right-most digit of $N$.

If $a_1=0$, then $a_0=[f(a_0,d)]$, so $a_0=0,1.$

If $a_1\not=0$, then $a_0=[a_1+f(a_0,d)]$, so $a_0=a_1+1$ where $a_1\not=9$.

Answer 2

An attempt:

Fix $d \in [1,9] \subset \Bbb{R}$. Allow me to rewrite your function a bit: $$h(n) = f(n) -n$$ where $n \in \mathbb{N}$ and $f(n)$ is recursively defined.

$$f(n) = \begin{cases} n<0\quad f(-n) \\ n=0\quad 0\\ 0<n<10\quad 1\\ n≥10\quad x \delta_{\lfloor \frac n x \rfloor,d} + \lfloor \frac n x \rfloor f(x-1) + f(n \mod x) \end{cases}$$

where $x$ is a power of ten. (Specifically it has the number of digits of $n$ minus one zeros. Except for powers of ten! (then it's one less zero)). Hope that made sense.

Indeed we also have that $\lfloor \frac n x \rfloor$ is the leading digit of $n$ and $(n \mod x)$ is the number $n$ without its leading digit.

Need to find all roots of the function for every $d$.

UPDATED NOTES

1) $d \in \Bbb{Z}$

2) For a positive integer $n$ you will never get the first (negative) case.

3) You are going to get a lot of calls to $$f(9\dots9)$$ because $x-1$ and its children (in the final case) will always have that form.

4) The only thing that comes out of $f$ is the zero of case 2, the 1(s) from case 3 and the power of ten when your input (or its children) have a digit that matches the digit $d$.

4.5) Let $d \neq 9$ Then $$f(9999) = 9*f(999)+f(999) = 10*f(999) = 10*(10*f(99))$$ $$=10*(10*(10*f(9))) = 1000$$ by repeated application of the final case. Now let $d = 9$ Then $$f(9999) = 1000+10*f(999) = 1000 + 10*(100 + 10*f(99))$$ $$= 1000 + 10*(100 + 10*(10 + 10*f(9)) = 1000 + 10*(100 + 10*(10 + 10*1)$$ $$ = 4000 $$

The pattern here is clear for any number of nines.

4.75) General case: say $d = 3$ $$f(53643102) = 0 + 5*f(9999999) + f(3645102)$$ $$ = (5*1000000) + (1000000 + 3*f(999999) +f(645102)) = 6300000 +f(645102)$$ $$ = \cdots = 6365311$$

Where the pattern seems easy enough to calculate for the general case when $d \neq 9$

I think I've got this right. The rest was wrong.

I welcome some feedback on my analyses. Let me know if this is all rubbish.