Let $u(n)$ be the numbers of positive integers $k \le n$ such that the largest prime factor of $k+1$ is greater than the largest prime factor of $k$.

Similarly, let $l(n)$ be the numbers of positive integers $k \le n$ such that the largest prime factor of $k+1$ is smaller than the largest prime factor of $k$.

As we go higher up the number line, the density of primes decreases in accordance with the Prime Number Theorem. Since more natural numbers to be composed of small prime factors than with large prime factors I expected $u(n)$ to be much greater than $l(n)$. However, computation showed that their difference is much lesser than I expected. In fact,we have: $$ u(10000) = 5008, l(10000) = 4991 $$ $$ u(100000) = 50079, l(100000) = 49920 $$

In other words, even though density of primes thins out, natural numbers are such that the largest prime factors of two consecutive natural numbers are almost equally likely to greater of less than one another.

Question: What is the expected gap between $u(n)$ and $l(n)$ as per the Prime Number theorem?

  • 2
    $\begingroup$ Interesting, albeit possibly irrelevant to any proof, Hardy proved that the largest prime factor of any number $x$ is (Albers et al, 2015, p.226): $$\theta(x)=\lim_{r,m,k\to\infty}\sum_{i=0}^m\left(1-\left[\cos\frac{\pi(i!)^r}{x}\right]^{2k}\right).$$ $\endgroup$ – Antinous Aug 10 '17 at 7:04
  • 1
    $\begingroup$ The density of primes tell you very little about $u$ and $l$. If there were a big difference between the two, say $u \gg l$, then that would mean that as you walk along the number line, then $p(n)$ (the largest prime factor of $n$) would take many, small steps upward, and few, large steps down. Nothing about the prime number theorem says anything about whether the size of those steps correlates with the direction. The $abc$-conjecture might, though... $\endgroup$ – Arthur Aug 10 '17 at 7:05
  • $\begingroup$ Why would you expect "much larger". If $p\gt 2$ is a prime it has a larger prime factor than the numbers on either side. Likewise $3p$ has likely larger highest factor than the numbers on either side and certainly than one (because one will be divisible by $4$, and these will be evenly distributed between higher and lower than $3p$ looking at residues and applying Dirichlet's theorem on primes in arithmetic progression). Likewise if a number has only small prime factors one might expect the numbers on either side to have a larger factor. $\endgroup$ – Mark Bennet Aug 10 '17 at 7:46

Although you expect the largest prime factor of a $n$ to generally trend bigger as $n$ increases, first of all:

  • that growth is slow and highly erratic
  • perhaps more important for your puzzle, one of $k$ and $k+1$ is even, the other is odd. You'd kind of expect the odd number to have larger prime factors. Hence your $u(n)$ and $l(n)$ will be similar.

You could try defining $u(n)$ and $l(n)$ in terms of $k$ and $k+2$, to see if you get any interesting difference between them. I suspect not, but you never know.

In any case, testing up to small $n$ such as $n=10000$ tells you very little about long-term trends: see this article for example.


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.