Question about functions $f: \mathbb{Z}^+ \to \mathbb{Z}^+$ such that $x$ is prime whenever $f(x)$ is prime

Question

Let $f: \mathbb{\mathbb{Z}^+} \to \mathbb{Z^+}$ be a function and suppose

$(\star)$ For all integers $x \geq 3$, if $f(x)$ is prime, then $x$ is prime.

A trivial example of such a function is the identity $f(x) = x$. However, a possible non-trivial example which I have come across is \begin{align*} f(x) = \left\lfloor \frac{\cosh(x\ln(2 + \sqrt{3}))}{2}\right\rfloor. \end{align*}

This function seems to satisfies $(\star)$ (see OEIS A198196). I have two questions:

1. How might one go about proving $f$ satisfies $(\star)$? I'm not sure where to begin with this, and it seems like a difficult task.
2. Have functions with property $(\star)$ been studied before?

Thanks for any information you can give me.

---

Edits: I've composed the floor function with $f$, and added the condition to $(\star)$ that $x$ must be an integer.

Answer 1

As observed in comments, we have $f(n) = \lfloor g(n) \rfloor$ where $g(n) = \frac{\alpha^n + \alpha^{-n}}{4}$ and $\alpha = 2 + \sqrt{3}$. From the recurrence $g(n+1) = 4 g(n) - g(n-1)$ we see that $g(n)$ is a half-integer when $n$ is even and an integer when $n$ is odd. In fact we see from induction that for even $n$ we have $g(n) = \frac{1}{2} \hbox{ mod } 3$ and for odd $n$ we have $g(n) = 1 \hbox{ mod } 3$. Hence for even $n$, $f(n)$ is divisible by $3$ and thus not prime except when $n=2$. For odd $n$, we have $f(n)=g(n)$, and for odd $n,m$ we then have $$ f(nm) = f(n) (\alpha^{n(m-1)} + \alpha^{n(m-3)} + \dots + \alpha^{n(1-m)})$$ thanks to the formula $a^m+b^m = (a+b)(a^{m-1} + a^{m-2} b + \dots + b^{m-1})$. From the Galois group action interchanging $\alpha$ and $\alpha^{-1}$ we see that $\alpha^{n(m-1)} + \alpha^{n(m-3)} + \dots + \alpha^{n(1-m)}$ is an integer, and for $n,m \geq 3$ this integer is larger than $1$. Thus $f(nm)$ is composite when $n,m \geq 3$ are odd, so the only remaining possible values of $n$ for which $f(n)$ can be prime are the primes.

In the language of divisibility sequences, $f(n)$ is a divisibility sequence on the odd natural numbers, though not on the even ones. In retrospect this is not so surprising given that $f$ is so similar to the Fibonacci sequence $F_n = \frac{\phi^n - \phi^{-n}}{\sqrt{5}}$, which is well known to be a divisibility sequence.

Answer 2

Too long for a comment.

If you are restricting to $n$ being an integer, unless I made a mistake, the problem can be rephrased as Let $$a_{n+1}=4a_n-a_{n-1} \\ a_1=1 \\ a_0=\frac{1}{2}$$

Then, show that $\lfloor a_n \rfloor$ is prime implies that $n$ is prime.

Here are some notes, I didn't check the details so there may be many mistakes.

Note 1: I think that $a_{2n} \in \mathbb Z +\frac{1}{2}$ and $a_{2n+1} \in \mathbb Z$. This implies that $$ \lfloor a_{2n} \rfloor = a_{2n}-\frac{1}{2} \\ \lfloor a_{2n+1} \rfloor = a_{2n+1} $$

This suggests splitting the problem into odd and even $n$.

Note 2: The odd $n's$. Let $$ b_n=a_{2n+1}=\frac{(2-\sqrt{3})^{2n+1}+(2+\sqrt{3})^{2n+1}}{4}=\frac{(2-\sqrt{3})(7-4\sqrt{3})^{n}+(2+\sqrt{3})(7+4\sqrt{3})^{2n+1}}{4} $$ I think that this is the solution to the recurrence $$ b_{n+1}=14b_n-b_{n-1} \\ b_{1}= \mbox{something} \\ b_0=\mbox{something} $$

The problem then becomes

Question A Show that $b_{n}$ prime implies that $2n+1$ is prime.

Similarly, $$c_{n}=a_{2n}$$ is the solution to the same recurrence, with different innitial condition.

Setting $$ d_{n}=c_n-\frac{1}{2} $$ we get $$ c_{n}=d_n+\frac{1}{2} $$ and hence the recurrence becomes $$ c_{n+1}=14c_n-c_{n-1} \Rightarrow d_{n+1}=14d_n-d_{n-1}+6 $$ and the question becomes:

Question B: show that $d_n$ is not prime for $n \geq 2$.

There are some techniques of solving such problems for recurrences, so these comments could help or could be totally useless.

ANd keep in mind that there may be mistakes above.