@JosephO'Rourke asked a question about a Collatz like function related to primes:

$f(n) = \begin{cases} n^2 & \text{if} \;n \;\text{is prime} \\ \lfloor n/2 \rfloor & \text{if} \;n \;\text{is composite} \end{cases}$

@quid commented that (for prime $p$) "after a prime-induced increase there are (small exceptions aside) always at least four divisions as $2^33∣p^2−1$ for $p>3$." (@TheMaskedAvenger also noted in a comment that "$(6k\pm1)^2$ is $1\mod 24$, so there will be at least four halvings of $p^2$ for prime $p$ greater than $5$.")

Question. For every prime $p\ge13$, starting with $n=p^2-1$, are there always at least five divisions $n\mapsto\lfloor n/2 \rfloor$, before we reach a prime again?

Let $c(p)$ counts the number of divisions $n\mapsto\lfloor n/2 \rfloor$ starting with $p^2-1$ before we reach a prime.
For example, if $p=3$ then $p^2-1=8\mapsto4\mapsto2$, a prime, so $c(3)=2$ (for 2 divisions).
If $p=5$ then $p^2-1=24\mapsto12\mapsto6\mapsto3$, a prime, so $c(5)=3$ (for 3 divisions).
When $p=7$ then $p^2-1=48\mapsto24\mapsto12\mapsto6\mapsto3$, a prime, so $c(7)=4$ (for 4 divisions).

In this notation, @quid's comment amounts to the statement, I think, that $c(p)\ge4$ whenever $p\ge7$ is a prime. My question is whether $c(p)\ge5$ whenever $p\ge13$ is a prime. Here are a few more examples.

If $p=11$ then $p^2-1=120\mapsto60\mapsto30\mapsto15\mapsto7$, a prime, so $c(11)=4$.
If $p=13$ then $p^2-1=168\mapsto84\mapsto42\mapsto21\mapsto10\mapsto5$, a prime, so $c(13)=5$.
For $p=17$, $p^2-1=288\mapsto144\mapsto72\mapsto36\mapsto18\mapsto9\mapsto4\mapsto2$, a prime, so $c(17)=7$.
If $p=19$ then $p^2-1=360\mapsto180\mapsto90\mapsto45\mapsto22\mapsto11$, a prime, so $c(19)=5$.

A list of a few more values: $c(23)=8$, $c(29)=6$, $c(31)=7$, $c(37)=8$, $c(41)=7$, $c(43)=8$, $c(47)=7$, $c(53)=6$, $c(59)=8$, $c(61)=7$, $c(67)=8$, $c(71)=5$.

My computer confirmed so far that $c(p)\ge5$ for at least $13\le p\le29526443$ (I am using reduce computer algebra and its prime-testing predicate primep). On the other hand it seems that at least five divisions might be the best we could hope for. It looks that primes $p$ with $c(p)=5$ do occur with some regularity, even for what one might reasonably call large $p$. For example, $c(765432348377)=5$, $c(765432356153)=5$, $c(765432363769)=5$, $c(765432364793)=5$. Also, $c(765432345678765432345678987654323460199)=5$.

I asked the related MSE question whether $\dfrac{p^2-1}{24}$ is composite for all prime $p\ge17$. The answer turned out to be yes (easily, in hindsight), but then I realized that it was this question here that I wanted to ask, and which to me seems more difficult as $16$ need not always divide $p^2-1$ (even if $24$ does). Are there any known related results (and ... is the present question easy too)? Thank you for your help!

Meanwhile my computer confirmed that $c(p)\ge5$ for primes $13\le p\le40173409$.

Edit. As @Lucia indicated in a comment (why not post as an answer?) "Yes, this also follows easily by just dividing $p$ into the possible residue classes $(\mod8)$, and doing some simple algebra."
So I consider the question answered (though I have to verify the details for myself). One may also like to learn more about the values of $c(p)$, if there is anything one could come up with, but admittedly the latter is an open-ended question.

  • 5
    $\begingroup$ Yes, this also follows easily by just dividing $p$ into the possible residue classes $\pmod 8$, and doing some simple algebra. $\endgroup$
    – Lucia
    May 9, 2015 at 19:28
  • 1
    $\begingroup$ Yes, @Lucia, it is easy, thank you! Let me spell out the details. Case 1. $p=8t\pm1$ with $t\ge2$. Then $(8t\pm1)^2-1=64t^2\pm16t+1-1=16t(4t\pm1)\mapsto 8t(4t\pm1)\mapsto 4t(4t\pm1)\mapsto 2t(4t\pm1)\mapsto t(4t\pm1)\mapsto \bigl\lfloor \dfrac{t(4t\pm1)}2 \bigr\rfloor.$ $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $ Case 2. $p=8t\pm3$ with $t\ge2$. Then $(8t\pm3)^2-1=64t^2\pm48t+9-1=8(8t^2\pm6t+1)\mapsto 4(8t^2\pm6t+1)\mapsto 2(8t^2\pm6t+1)\mapsto (8t^2\pm6t+1)=2t(4t\pm3)+1\mapsto t(4t\pm3)\mapsto\bigl\lfloor \dfrac{t(4t\pm3)}2 \bigr\rfloor$. $\endgroup$
    – Mirko
    May 9, 2015 at 21:40


You must log in to answer this question.