Define $g(n)$ for an integer $n \ge 2$ to be the smallest positive integer with the following properties:
- $g(n)$ is not divisible by 3
- For all $2\le k \le n$, we have $\gcd(4^k-1,g(n))>1$
Then $g(2)=5$, $g(3)=g(4)=35$, $g(5)=385$. The growth of this function is relevant to the question of whether there are or are not infinitely many solutions to the Freudenthal Problem.
A naive way to define $g(n)$ as a recurrence is to first find the smallest factor $p$ of $(4^n-1)/3$ and then set $g(n)=\left\{ \begin{array}{11} p g(n) & \gcd(p, g(n-1))=1\\ g(n) & \gcd(p, g(n-1))>1 \end{array} \right.$
However, computing factorizations of large numbers gets difficult quickly.
It is clear that if $n$ is composite, $g(n)=g(n-1)$. Using cycles of $r\rightarrow 4r+3 \pmod{2n+1}$ one can also show that if both $n$ and $2n+1$ are prime, $g(n)=(2n+1)g(n-1)$.
Where I am stumped is the case where $n$ is prime and $2n+1$ is composite. In some instances, one has $g(n)=(cn+1)g(n-1)$ for some $c$, while in others $g(n)=\frac{2^n+1}{3}g(n-1)$. For example, $g(37)/g(36)=223$, while $g(17)/g(16)=43691$. I struggle to see why the former incurred a "small" factor, while the latter the worst case "large" factor, as $6*37+1=223$ and $6*17+1=103$ are both prime.
The question of the growth of $g(n)$ hinges on being able to predict how often it acquires a large factor of order $2^n$ rather than one of order $n$. Is there something I am missing that makes this more readily computable/understandable?