Did someone say coprime?

Let $k=\pi(n)$ be the number of primes at most $n$, and $P$ be their product. The question asks for a number coprime to $P$ within a certain range. Gerry Myerson notes that one conjecturally has to test only about $(\log n)^2$ numbers for primality. I recommend more explicitly looking near a chosen number $d$ for a number $c$ that is coprime to $P$.

Estimates by Iwaniec shows $c-d$ is $O((k\log k)^2)$, however the constant is not known to me. An uglier but explicit (and not entirely original) estimate is hiding behind a link at MathOverflow question 37679, and a weak version is that $c-d$ is (for $k$ not too small) less than $k^{3.81 \log\log k}$. So a brute force algorithm still has to check a lot of numbers, but not as many as $n^{O(n^\epsilon)}$.

Indeed, by sieving around $d$, one can cut the number of candidates to be tested for coprimality by a sizable fraction. The problem is now to build $P$ and check $\gcd(P,c)=1$. One can take a product of c's, find the common divisor of this product with $P$, and use that information to rule out false candidates. However, that could still be $O(n)$ many bits to play with.

If you are freely willing to let go of determinism, you can try some dynamic systems to generate candidates. One is iterations of the Collatz function on a seed $d$, one is choosing one or more low degree irreducible polynomials and feeding values to them in hopes of finding a coprime, and another is bit concatenation. Take the operation $ f(n) = \lfloor n/2 \rfloor $, and form the bit string from bit strings for $n,$ $f(n),$ $f(f(n)),$ and whatever combination of iterates you choose, for a candidate to be coprime. Again, testing for coprimality will be expensive.

Gerhard "Didn't Say Jacobsthal This Time" Paseman, 2017.09.13.

5more comments