HMMT February

We remark that $$f\left(n^{2}-1\right)=\max (f(n-1), f(n+1))$$ Let $X$ be a random variable that evaluates to $f(n)$ for a randomly chosen $2 \leq n \leq 10^{6}$; we essentially want to estimate $$\frac{\mathbb{E}\left[\max \left(X_{1}, X_{2}\right)\right]}{\mathbb{E}\left[X_{3}\right]}$$ where $X_{i}$ denotes a variable with distribution identical to $X$ (this is assuming that the largest prime factors of $n-1$ and $n+1$ are roughly independent). A crude estimate can be compiled by approximating that $f(n)$ is roughly $10^{6}$ whenever $n$ is prime and 0 otherwise. Since a number in this interval should be prime with "probability" $\frac{1}{\ln 10^{6}}$, we may replace each $X_{i}$ with a Bernoulli random variable that is 1 with probability $\frac{1}{\ln 10^{6}} \sim \frac{1}{14}$ and 0 otherwise. This gives us an estimate of $$\frac{1 \cdot \frac{2 \cdot 14-1}{14^{2}}}{\frac{1}{14}}=\frac{27}{14}$$ However, this estimate has one notable flaw: $n-1$ and $n+1$ are more likely to share the same primality than arbitrarily chosen numbers, since they share the same parity. So, if we restrict our sums to only considering $f(n)$ for odd numbers, we essentially replace each $X_{i}$ with a Bernoulli random variable with expectation $1 / 7$, giving us an estimate of $\frac{13}{7}$, good for 5 points. This estimate can be substantially improved if we consider other possible factors, which increases the correlation between $f(n-1)$ and $f(n+1)$ and thus decreases one's estimate. The correct value of $N$ is 18215.