Proof. We have $f(1) = 1$ and $f(2) = 2 f(1) = 2$ . Note that

$$ \begin{align*} f(4)f(5) &= f(20) = f(10) + f(10) = 2 f(2)f(5) = 4f(5), \\ f(11) &= f(1) + f(10) = 1 + 2f(5). \end{align*} $$

Thus, $f(5) = 0$ if and only if $f(11) =1$ .

If $f(5) = 0$ , then $f(11) = 1$ , so $f(23) = f(1) + f(2) f(11) = 3$ . However, this contradicts

$$ \begin{align*} f(2) f(23) = f(46) = f(1) + f(9)f(5) = 1. \end{align*} $$

Hence, $f(5) \neq 0$ and $f(4)=4$ . Moreover,

(2.1) $$ \begin{align} 1+ f(9)f(5) = f(2)f(23) & = 2 ( f(1) + f(2)f(11)) \notag \\ & = 2 (1 + 2f(11)) = 2 + 4(1 + 2 f(5)) = 6 + 8 f(5). \end{align} $$

From

$$ \begin{align*} f(2)f(5) + f(9)f(5) = f(10) + f(45) = f(55) = f(5)f(11) = f(5) (1+ 2f(5)), \end{align*} $$

we obtain

$$ \begin{align*} f(9) = 2f(5) -1. \end{align*} $$

Thus,

(2.2) $$ \begin{align} 1+ f(9)f(5) = 1 + 2f(5)^2 - f(5). \end{align} $$

Combining (2.1) and (2.2) gives

$$ \begin{align*} (2f(5) + 1) (f(5) - 5) = 0, \end{align*} $$

so $f(5) = -1/2$ or $f(5)=5$ .

From

$$ \begin{align*} f(5)f(11) &= f(45) + f(10) = f(5)f(9) + f(5)f(2), \\ f(23) &= f(22) + f(1) = 2f(11) + 1, \\ f(4)f(29) &= f(116) = f(115) + f(1) = f(5)f(23) + 1, \\ f(29) &= f(7) + f(22) = f(7) + 2 f(11), \end{align*} $$

we obtain

$$ \begin{align*} f(5) &= 5, \quad f(11) = 11, \quad f(9) = 9, \quad f(23)=23 ,\quad f(29)=29, \quad f(7)=7, \\ f(5) &= -\frac{1}{2}, \quad f(11)=0, \quad f(9)=-2, \quad f(23)=1,\quad f(29)=\frac{1}{8}, \quad f(7)= \frac{1}{8}. \end{align*} $$

The latter case leads to a contradiction. Indeed,

$$ \begin{align*} f(7)f(11) &= f(76) + f(1) = 4f(19) + 1, \\ f(7)f(19) &= f(126) + f(7) = f(2)f(7)f(9) + f(7). \end{align*} $$

Using

$$ \begin{align*} f(17) &= f(7) + f(2)f(5), \\ f(32) &= f(2)f(11)+ f(2)f(5), \\ f(4)f(7) &= f(28) = f(27) + 1, \\ f(32)f(11) &= f(351) + f(1) = f(27)f(13) + 1, \\ f(8)f(25) &= f(85) + f(115) = f(5)f(17) + f(5)f(23), \\ f(16)f(11) &= f(7)f(25) + 1, \\ f(2)f(31) &= f(10) + f(4)f(13), \end{align*} $$

we conclude that $f(n) = g(n)$ for $n \leq 32$ .

Proof. We already know that $f(9)=9$ .

Suppose $k=2r$ , with $r \geq 2$ . Then,

$$ \begin{align*} D_{3^r} + D_{-3^r} = 3^{r+1} (4 \cdot 3^{r-1} - 1) + 3^{r+1} (4 \cdot 3^{r-1} + 1) = 8 \cdot 3^{2r}. \end{align*} $$

Since $3^{r+1} \leq 3^{2r-1}$ and $4 \cdot 3^{r-1} \pm 1 < 3^{2r-1}$ , it follows that $f(3^{2r}) = 3^{2r}$ .

Suppose $k=2r+1$ . Since we have $f(27)=27$ , we may assume $r \geq 2$ . Note that $3^{2r} \equiv \pm 1 \pmod {10}$ . Assume that $3^k = 3(10m + 1)$ for some integer $m \geq 8$ . Consider

(2.3) $$ \begin{align} D_{m+1} + D_{-3m} = (m+1)(4m+1) + 9m(4m+1) = (10m+1)(4m+1). \end{align} $$

Since $9 \mid 10m+1$ , we have $m \equiv -1 \pmod {9}$ and $4m+1 \equiv -3 \pmod {9}$ . Thus,

$$ \begin{align*} \gcd(m+1,4m+1) = \gcd(9m, 4m+1) = \gcd(10m+1, 4m+1) = 3. \end{align*} $$

Rewriting (2.3),

$$ \begin{align*} (3m+3)\bigg( \frac{4m+1}{3} \bigg) + 27m\bigg( \frac{4m+1}{3} \bigg) = 3^k \bigg( \frac{4m+1}{3} \bigg). \end{align*} $$

Since $27, m, 3m+3, (4m+1)/3 < 10m+1 = 3^{2r}$ , we obtain $f(3^k) = 3^k$ .

A similar argument using

$$ \begin{align*} D_{-m+1} + D_{3m} = (m-1)(4m-1) + 9m(4m-1) = (10m-1)(4m-1) \end{align*} $$

shows that if $3^k = 3(10m - 1)$ for some integer $m> 1$ , then $f(3^k) = 3^k$ .

Proof. We already know that $f(5) =5$ and $f(25) = 25$ .

Suppose $k = 2r$ , with $r \geq 2$ . Consider

$$ \begin{align*} D_{5^r} + D_{-5^r} = 5^{r} (4 \cdot 5^{r} - 3) + 5^{r} (4 \cdot 5^{r} + 3) = 8 \cdot 5^{2r}. \end{align*} $$

Since $5^r, 4 \cdot 5^{r} \pm 3 < 5^{r+1} \leq 5^{2r-1}$ , it follows that $f(5^{2r}) = 5^{2r}$ .

Suppose $k = 2r+1$ , where $r \geq 1$ . Write $5^{2r} = 4m+1$ for some $m \geq 6$ with $5 \nmid m$ . Consider

$$ \begin{align*} D_{-3m} + D_{5m+2} = 9m(4m+1) + (5m+2)(20m+5) = 2(4m+1)(17m+5), \end{align*} $$

where $9m, 4m+1, 5m+2, 17m+5 < 20m+5 = 5^{k}$ .

If $3 \mid m$ , we write $m = 3^u d$ for some $d \geq 1$ , $3 \nmid d$ . Then, $f(9m) = f(3^{u+2})f(d) = 3^{u+2}d = 9m$ , and since $3 \nmid (4m+1)(5m+2)(17m+5)$ , we have $f(a) = a$ for $a \in \{ 4m+1, 5m+2, 17m+5 \}$ .

If $3 \nmid m$ , then $f(9m) = f(9)f(m) = 9m$ . If $m \equiv 2 \pmod {3}$ , then

$$ \begin{align*} 5^{2r} = 4m+ 1 \equiv 0\quad \pmod{3}, \end{align*} $$

which is a contradiction. Thus, $m \equiv 1 \pmod {3}$ and $3 \nmid (4m+1)(5m+2)(17m+5)$ .

In all cases, it follows that $f(5^k) = 5^k$ .

Proof. It is easy to show that (2.4) has the unique solution $(x,y)= (1,1)$ . Indeed, assuming $x \geq 2$ and reducing the equation modulo $4$ leads to a contradiction. For (2.5), it is readily verified that $(x,y) = (2,0), (3,1)$ and $(7,3)$ are solutions. By [Reference Scott and Styer10, Theorem 4], the equation has at most one solution in positive integers $(x,y)$ with $y>1$ . Hence, these constitute all solutions.

Proof. Since $f(2^k) = 2^k$ for $1 \leq k \leq 5$ , we may assume $k \geq 6$ .

Suppose $k = 2r+1$ , with $r\geq 3$ . Consider

$$ \begin{align*} D_{2^{r-1}} + D_{-2^{r-1}} = 2^{r-1} (2^{r+1} - 3) + 2^{r-1} (2^{r+1} + 3) = 2^{2r+1}, \end{align*} $$

with $2^{r-1} < 2^{r+1} - 3< 2^{r+1} + 3 < 2^{k-1}$ . Thus, $f(2^k) = 2^k$ .

Suppose k is even. Then, $2^{k+1} \equiv \pm 3 \pmod {5}$ .

If $2^{k+1} \equiv 3 \pmod {5}$ , consider

$$ \begin{align*} D_{2^{k-1}} + D_{2^{k-1}} = 2^{k-1}(2^{k+1}-3) + 2^{k-1}(2^{k+1}-3) =2^k ( 2^{k+1} - 3). \end{align*} $$

By Lemma 2.4, the only nonnegative solutions of $2^x - 3 = 5^y$ are $(x,y) \in ~\{ (2,0), (3,1), (7,3) \}$ . In addition, $q \nmid 2^{k+1} - 3$ for $q=2,3$ . We write $2^{k+1} - 3 = 5^u d$ with $u \geq 1$ , $d \geq 7$ and $5 \nmid d$ . Then,

$$ \begin{align*} 2^{k-1} 5^u d + 2^{k-1} 5^u d =2^k 5^u d, \end{align*} $$

where

$$ \begin{align*} d = \frac{2^{k+1} - 3}{5^u} < \frac{2^{k+1}}{5^u} < 2^{k-1} \quad \text{and}\quad 5^u = \frac{2^{k+1} - 3}{d} < \frac{2^{k+1}}{7} < 2^{k-1}. \end{align*} $$

Thus, $f(2^k) = 2^k$ .

If $2^{k+1} \equiv -3 \pmod {5}$ , a similar argument using

$$ \begin{align*} D_{-2^{k-1}} + D_{-2^{k-1}} = 2^{k-1}(2^{k+1}+3) + 2^{k-1}(2^{k+1}+3) =2^k ( 2^{k+1} + 3), \end{align*} $$

and the fact that $2^x + 3 = 5^y$ has the unique solution $(x,y)=(1,1)$ yields $f(2^k) = 2^k$ .

Proof. Suppose $k=2r$ , with $r \geq 1$ . Consider

$$ \begin{align*} D_{p^r} + D_{-p^r} = p^r(4p^r -3) + p^r (4p^r + 3) = 8p^r, \end{align*} $$

with $p^r, 4p^r \pm 3 < p^{r+1} < p^k$ . Hence, $f(p^k) = p^k$ .

Suppose k is odd, so $p^k \equiv \pm 1, \pm 3 \pmod {10}$ .

Assume that $p^k =10m+1$ for some positive integer m. Since we already know that $f(q) = q$ for $q = 11, 31$ , we may assume that $m \geq 4$ . Consider

$$ \begin{align*} D_{m+1} + D_{-3m} = (m+1)(4m+1) + 9m(4m+1) = (10m+1)(4m+1), \end{align*} $$

with $m+1, 4m+1, 9m < 10m+1 = p^k$ . If $m \equiv 2 \pmod {3}$ , then $p^k = 10m+1 \equiv 0 \pmod {3}$ , which is contrary to our assumption on p. Hence, $m \not \equiv 2 \pmod {3}$ and

$$ \begin{align*} \gcd(m+1, 4m+1) = \gcd(9m, 4m+1) = \gcd(4m+1, 10m+1) = 1. \end{align*} $$

Thus, $f(p^k) = p^k$ .

By a similar argument using the equation

$$ \begin{align*} D_{-m+1} + D_{3m} = (m-1)(4m-1) + 9m(4m-1) = (10m-1)(4m-1), \end{align*} $$

it can be shown that if $p^k = 10m-1$ , then $f(p^k) = p^k$ .

Next, assume that $p^k = 10m+3$ for some positive integer m. Since we have $f(q)=~q$ for $q=13,23$ , we may assume that $m \geq 3$ . Consider

$$ \begin{align*} D_{-m} + D_{-3m} = m(4m+3) + 9m(4m+1) = 4m(10m+3), \end{align*} $$

where $m, 4m, 4m+1, 4m+3, 9m < 10m+3 = p^k$ . Since $3 \nmid m$ ,

$$ \begin{align*} \gcd(m,4m+3) = \gcd(9m, 4m+1) = \gcd(4m, 10m+3) = 1, \end{align*} $$

so $f(p^k) = p^k$ .

By a similar argument using the equation

$$ \begin{align*} D_{m} + D_{3m} = m(4m-3) + 9m(4m-1) = 4m(10m-3), \end{align*} $$

it can be shown that if $p^k = 10m-3$ , then $f(p^k) = p^k$ . This completes the proof of the lemma and of the main theorem.