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

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.

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.

• Thanks for this! It was a terrific answer, very helpful. One question: in your restatement of my conjecture, did you mean $F(2n,k)\leq 2F(n,k)$ or should that have been a $<$? If I'm following this correctly, it seems like I'd need that to enforce the strictly-less-than relationship I'm positing. – Trevor Feb 6 at 9:45
• You are quite right. I stated the conjecture in the weaker form was because equality holds for 'large' $k$ which are irrelevant for your problem. So what happens is that we have initially have a strict inequality and then, as we deal with all the larger primes (dividing $2n$ but not $n$), the 'gap' gradually reduces to zero. – S. Dolan Feb 6 at 10:15
• So the Conjecture is strongly related to your result but not 'equivalent' and I've removed that word from the post. – S. Dolan Feb 6 at 10:20
• The sequence $[1,n]$ has a few nice traits, and one of them is that it starts off $\equiv 1 \pmod{k}$ for any $k$; as such, it is guaranteed to contain at most the same amount of a given factor as does any higher consecutive sequence, like $[n+1,2n]$. Doesn't this property make $F(2n,k)\leq 2F(n,k)$ always true, or am I missing something? – Trevor Feb 7 at 1:07
• What I think makes it trickier is that factors can 'interfere' with each other in this type of argument. E.g.Consider $n=10$ for factors $3$ and/or $5$. $n=10$ contains the same number of multiples of $3$ as $n+1,2n$ and the same is true for multiples of $5$. However, $[1,n]$ contains more multiples of $3$ and/or $5$. – S. Dolan Feb 7 at 10:02