Does there exist a $k \in \mathbb{R}$ such that for all $n \in \mathbb{N}, n \ge 3$, $\text{gpf}(\lfloor n^{(\log{n})^k} \rfloor) \gt n$, where $\text{gpf}(x)$ is the greatest prime factor of $x$?

I am interested because I was trying to figure out if a polynomial-time algorithm for factoring $n$ implies the existence of a polynomial-time algorithm to find a prime greater than $n$. If $k$ has quickly-computable approximations, then we could accomplish this by calculating $\lfloor n^{(\log{n})^k} \rfloor$ and factoring it, since the size of the representation of that number (its logarithm) is polynomial in the size of the representation of $n$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.