2
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ I think that $f(n,d)$ is not defined for $n=10$. Also, $0\lt n\lt 10$ instead of $n\lt 10$? Also, since $n\in\mathbb N$, we have $n\ge 0$, don't we? $\endgroup$
    – mathlove
    Dec 5 '15 at 10:03
  • $\begingroup$ @mathlove Yeah, it should really be $n > 9$. The $>0$ part is just for the sake of clearness. $\endgroup$
    – Sebb
    Dec 5 '15 at 11:33
  • $\begingroup$ You are using $n\lt 10$. Note that this includes $n=0$. Shouldn't $n\lt 10$ be $0\lt n\lt 10$? $\endgroup$
    – mathlove
    Dec 5 '15 at 11:37
  • $\begingroup$ @mathlove I'm from a programming background, so I thought that this case would be covered by $n = 0$ beforehand ;) But I'll fix it, thanks. $\endgroup$
    – Sebb
    Dec 5 '15 at 13:10
  • $\begingroup$ you probably have a typo somewhere because you always have $x \le n/10$, $y\ge 10$, and so $g(y,d)=0$ forall $d$. $\endgroup$
    – mercio
    Dec 5 '15 at 13:14
1
+50
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ Impressive. Thanks a lot! $\endgroup$
    – Sebb
    Dec 10 '15 at 21:10
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ You're pretty much right :) A lot of this function is to extract the leading digit from the rest of the function & $d$ is meant to be an integer. The calls to $f(9...9)$ are actually a nice side effect since I can easily cache those. 4) to 7) are interesting points, got to think about this. Unfortunately I can't pinpoint what the function is supposed to do, since it's for a math challenge where you're supposed to be quiet about solutions. $\endgroup$
    – Sebb
    Dec 8 '15 at 21:28
  • $\begingroup$ I think I've got most of your function figured out Need to finish the last bit $d = 9$ part. $\endgroup$
    – amcalde
    Dec 9 '15 at 2:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.