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.

  • 4
    $\begingroup$ 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. $\endgroup$
    – Nick S
    Jun 17, 2021 at 18:28
  • 2
    $\begingroup$ Yes. For example, $f(x)=17$ when $x=3.2038164\dots$, which is not prime. $\endgroup$ Jun 17, 2021 at 18:31
  • 2
    $\begingroup$ @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. $\endgroup$
    – Nick S
    Jun 17, 2021 at 18:35
  • 2
    $\begingroup$ @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. $\endgroup$
    – Nick S
    Jun 17, 2021 at 18:59
  • 8
    $\begingroup$ 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. $\endgroup$ Jun 17, 2021 at 20:04

2 Answers 2


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.

  • $\begingroup$ 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? $\endgroup$ Jun 18, 2021 at 0:49
  • 11
    $\begingroup$ 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. $\endgroup$
    – Terry Tao
    Jun 18, 2021 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.

  • $\begingroup$ Thank you for your answer. I believe the original recurrence relation is off since $f(3) =13$ but $a_{3}=19$. $\endgroup$ Jun 17, 2021 at 20:59
  • 1
    $\begingroup$ 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 :) $\endgroup$
    – Nick S
    Jun 17, 2021 at 23:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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