Problem 820

Erdős Problem #820: declared status 'open'. Formalized: no. Let $H(n)$ be the smallest integer $l$ such that there exist $k<l$ with $(k^n-1,l^n-1)=1$. Is it true that $H(n)=3$ infinitely often? (That is, $(2^n-1,3^n-1)=1$ infinitely often?) Estimate $H(n)$. Is it true that there exists some constant $c>0$ such that, for all $\epsilon>0$,$$H(n) > \exp(n^{(c-\epsilon)/\log\log n})$$for infinitely many $n$ and$$H(n) < \exp(n^{(c+\epsilon)/\log\log n})$$for all large enough $n$? Does a similar upper bound hold for the smallest $k$ such that $(k^n-1,2^n-1)=1$? Current best: van Doorn in the comments sketches a proof of the lower bound: that there exists some constant $c>0$ and infinitely many $n$ such that$$H(n) > \exp(n^{c/\log\log n}).$$The sequence $H(n)$ for $1\leq n\leq 10$ is$$3,3,3,6,3,18,3,6,3,12.$$The sequence of $n$ for which $(2^n-1,3^n-1)=1$ is A263647 in the OEIS. Prize: no. OEIS: A263647. Tags: number theory.