Do all elements of $[n+1,2n]$ have strictly higher gpf than elements of $[1,n]$ when sorted by gpf?

Question

For any $n\in\mathbb N$, let $A=\{x\in\mathbb N \mid 1 \leq x \leq n\}$ and $B=\{x\in\mathbb N \mid n+1 \leq x \leq 2n\}$.

Order the sets by greatest prime factor of each element, ascending. Let $A_1$ be the element in $A$ with the smallest gpf and $A_n$ be the largest, and likewise for $B$.

Conjecture: $\mathrm{gpf}(A_k)<\mathrm{gpf}(B_k)$ for all $1 \leq k \leq n$.

e.g. Let $n=5$, and we have:

$$ \begin{array}{|l|l|l|l|} \hline A_k&\mathrm{gpf}(A_k)&\mathrm{gpf}(B_k)&B_k\\ \hline 1&1&2&8=2^3\\ \hline 2&2&3&6=2\cdot 3\\ \hline 4&2&3&9=3^2\\ \hline 3&3&5&10=2\cdot 5\\ \hline 5&5&7&7 \\ \hline \end{array} $$

where $\mathrm{gpf}(B_k)$ is strictly greater than $\mathrm{gpf}(A_k)$.

I confirmed this empirically for $n<3000$. Informally, it looked like the trends strongly suggest it won't fail at any point.

If this is a known result or conjecture, please share. Otherwise, I'm looking for counterexamples or any advice on how a proof could be approached$-$or a reason why a proof is likely to be difficult or impossible, as seems more typical with this stuff.

---

Quicky data tables for $n<70$ are here.

Answer 1

This is a very interesting observation about the divisors of numbers. I have looked at it in a slightly different way from you and I believe there is good reason to think that not only is it true but that it becomes more and more 'obvious' as $n$ becomes large.

You have asked for any advice on how a proof could be approached. I think the following is a good way to go about this but it is not totally straightforward. Please feel free to ask if anything is unclear.

Let $p_i$ denote the $i$th prime. For any positive integer $n$, define $F(n,k)$ to be the number of positive integers less than or equal to $n$ which are divisible by no prime $p_i$, for $i>k$. Then your result depends on the following result.

CONJECTURE $F(2n,k)\le 2 F(n,k)$ for all positive integers $n$ and $k$.

Results for small $k$ such as $F(n,0)=1$ and $F(n,1)=t+1$, where $2^{t+1}>n\ge 2^t$, indicate why the Conjecture is likely to be true.

It may be possible to prove this conjecture by induction by using the following recurrence relation.

RESULT For $n\ge p_k$, $F(n,k)= F(\left \lfloor{\frac{n}{{p_k}}}\right \rfloor ,k)+ F(n,k-1)$

Proof This follows by considering separately those positive integers less than or equal to $n$ which are divisible by $p_k$ and those which are not.

The snag in using this result to obtain a rigorous proof of the Conjecture is that we can have $ \left \lfloor{\frac{2n}{{p_k}}}\right \rfloor= 2\left \lfloor{\frac{n}{{p_k}}}\right \rfloor+1$. However, I hope this will be of some use.