5
$\begingroup$

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?

$\endgroup$
4
  • 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$
    – pshmath0
    Aug 10, 2017 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, 2017 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, 2017 at 7:46
  • $\begingroup$ n and n+1 have no common divisor, therefore their largest divisors are different. I expect very little variation due to the growing size of n. However, for example u(l) grows faster if there are consecutive numbers with increasing largest divisor, and there might be some preference that largest divisors tend to grow by small amounts then drop by a large amount. $\endgroup$
    – gnasher729
    Feb 1 at 16:35

1 Answer 1

Reset to default
0
$\begingroup$

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.

$\endgroup$
1

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .