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

Apologies for the clunky title.

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.

• Isn't $f(x)=\frac{(2-\sqrt{3})^{x}+(2+\sqrt{3})^{x}}{4}$. Also OEIS defines $f$ as the floor of this function, otherwise if $f(x)$ is prime, $x$ is probably sometimes irrational....Note here that this formula implies that, $f(n)$ satisfies, if I didn't make a mistake, the recurrence $$f(n+1)=4f(n)+f(n-1)$$ which may make the problem of studing for which integers $n$ is $f(n)$ prime easier. Going ro reals is a bit tricky though. Jun 17 '21 at 18:28
• Yes. For example, $f(x)=17$ when $x=3.2038164\dots$, which is not prime. Jun 17 '21 at 18:31
• @Joe Let $y:= (2+\sqrt{3})^x$. Then, you can solve the quadratic equation $$y+\frac{1}{y}=4f(x)$$ for $y$, and take the logarithm, to find the formula of $f^{-1}(x)$.... Or you can express $\cosh^{-1}$ in terms of elementary functions.... Note that since $\cosh$ is even, you get two solutions , one being minus the other. Jun 17 '21 at 18:35
• @mattstokes If you restrict to $n$ being an integer, you have the recurrence $$a_{n+1}=4a_n+a_{n-1} \\ a_1=1 \\ a_0=\frac{1}{2}$$ and you want to show that $\lfloor a_n \rfloor$ is prime implies $n$ is prime. If I am not mistaken $a_n$ is integer for odd $n$ and half integer for even $n$. I wonder if finding separate recurrences for $\lfloor a_{2n} \rfloor$ and $a_{2n+1}$ may make the problem easier. Jun 17 '21 at 18:59
• You might be interested in the notion of a divisibility sequence. This is a function from $\mathbb{Z}_{>0}$ to itself such that if $n \mid m$ then $f(n) \mid f(m)$. If $f(m)>1$ for $m>1$ then $f(n)$ being a prime implies $n$ is a prime. A classical example is $f(n)=2^n-1$, related to Mersenne numbers. Jun 17 '21 at 20:04

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.

• Thank you for the answer! Just one more related question: How much money would you bet on there being infinitely many primes $p$ such that $f(p)$ is prime? Jun 18 '21 at 0:49
• This is comparable to the open question of whether there exist infinitely many Mersenne primes, or infinitely many Fibonacci primes. Heuristics point in the direction of a positive answer to all these questions, but only barely (these heuristics predict that the number of primes in the first $x$ elements of each sequence grow only like $\log \log x$ or so), so I would not be as definitively certain of this as, say, the infinitude of twin primes. Jun 18 '21 at 0:56

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.

• Thank you for your answer. I believe the original recurrence relation is off since $f(3) =13$ but $a_{3}=19$. Jun 17 '21 at 20:59
• Yea, $2 \pm \sqrt{3}$ are roots of $x^2-4x+1=0$ which means that the recurrence is $a_{n+1}=4a_n-a_{n-1}$. Got the wrong signs, will fix it :) Jun 17 '21 at 23:20