8
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Trevor Feb 6 at 9:45
  • 1
    $\begingroup$ 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. $\endgroup$ – S. Dolan Feb 6 at 10:15
  • $\begingroup$ So the Conjecture is strongly related to your result but not 'equivalent' and I've removed that word from the post. $\endgroup$ – S. Dolan Feb 6 at 10:20
  • $\begingroup$ 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? $\endgroup$ – Trevor Feb 7 at 1:07
  • 1
    $\begingroup$ 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$. $\endgroup$ – S. Dolan Feb 7 at 10:02

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.