What is the probability that the greatest prime factor of a sequence of uniformly distributed integers increases?

Question

Let $f_k(n), n = 1,2,3...$ be a sequence of random integer uniformly distributed in $[2,k]$ for some fixed $k \ge 3$. Let $l_n$ be the largest prime factor of $f_k(n)$. What is the probability that $l_{n+1} > l_n$? Experimental data shows that as $k$ increases, the probability approaches $1/2$ while for each smaller values of $k$ the empirical probabilities approaches the following values:

$$ k = 3, P \approx 1/4 \\ k = 4, P \approx 2/9 \\ k = 5, P \approx 5/16 \\ k = 6, P \approx 8/25 \\ k = 7, P \approx 13/36 \\ k = 8, P \approx 17/49 \\ k = 9, P \approx 22/64 \\ k = 10, P \approx 29/81 \\ k = 10^6, P \approx 0.4995 \\ k = 10^8, P \approx 0.4998 \\ $$

Question: Is there a closed form in terms of $k$ for the probability $P(l_{n+1} > l_n)$? For small value of $k$, the denominator appears to be $(k-1)^2$ which suggests that there could be a closed form whose limiting value as $k \to \infty$ is $1/2$. I could not find the sequence of the numerators in OEIS.

SageMath Code

k = 10
t1 = randrange(2,1+k)
t2 = randrange(2,1+k)
f1 = prime_factors(t1)
f1 = f1[len(f1) - 1]
g = 0
i = 0
step = 10^6
target = step

while True:
    i = i + 1
    f2 = prime_factors(t2)
    f2 = f2[len(f2) - 1]
    
    if f2 > f1:
        g = g + 1
    
    if i == target:
        print(i, g/i.n())
        target = target + step
    
    t1 = t2
    f1 = f2
    t2 = randrange(2,1+k)

Answer 1

The $n$ is not really a meaningful part of the question. Really you're just taking two random integers in $[2,k]$ and comparing their highest factor. The occurence of $(k-1)^2$ in the denominator is thus just an artefact of the sample space. Some simple cases are illustrative: Fix $k$, and let $X,Y$ be random integers in $[2,k]$. We write a tick if the largest prime factor of $X$ is bigger than the largest prime factor of $Y$, and a cross otherwise.

$$ \begin{array} {|r|r|}\hline & 2 & 3 \\ \hline 2 & \times & \checkmark \\ \hline 3 & \times & \times \\ \hline \end{array} $$

$$ \begin{array} {|r|r|}\hline & 2 & 3 & 4 \\ \hline 2 & \times & \checkmark & \times \\ \hline 3 & \times & \times & \times \\ \hline 4 & \times & \checkmark & \times \\ \hline \end{array} $$

giving the results $1/4$, $2/9$ respectively.

Recall that an $n$-smooth number is an integer whose prime factors are all less than or equal to $n$. Say a number is "strictly" $n$-smooth if it is $n$-smooth and not $n-1$-smooth.

In general, the tables above can be extended to all integers, and the sample space for a given $k$ is just the upper-left $k\times k$ grid. Say $x$ goes along the top and $y$ along the side.

• If $x$ is a power of 2, then no $y$ contributes to the probability, because no number has a prime factor strictly less than 2.
• If $x$ is strictly 3-smooth, then all 2-smooth numbers contribute to the probability.
• If $y$ is strictly 5-smooth, then all 3-smooth numbers contribute to the probability.
• And so on, for each prime up to $k$.

I'm not sure whether there's an explicit formula for the probability. I think you can prove the limiting behaviour, though. Below I have extended the table up to $k=10$.

$$ \begin{array} {|r|r|}\hline & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline 2 & = & > & = & > & > & > & = & > & > \\ \hline 3 & < & = & < & > & = & > & < & = & > \\ \hline 4 & = & > & = & > & > & > & = & > & > \\ \hline 5 & < & < & < & = & < & > & < & < & = \\ \hline 6 & < & = & < & > & = & > & < & = & > \\ \hline 7 & < & < & < & < & < & = & < & < & < \\ \hline 8 & = & > & = & > & > & > & = & > & > \\ \hline 9 & < & = & < & > & = & > & < & = & < \\ \hline 10 & < & < & < & = & < & > & < & < & = \\ \hline \end{array} $$

Rather than just saying "bigger" or "not bigger" I've populated each cell with whether $X=Y$, $X>Y$ or $X<Y$. This has the advantage that the table is "antisymmetric": A $>$ in position $(i,j)$ implies a $<$ in position $(j,i)$, vice versa. As a result, the limiting probability $P_>$ is just

$$P_> = \frac12 (1-P_=)$$

and we're done if $P_=$ (the probability of choosing elements with an equal highest prime factor) is 0 in the limit. Denote by $\Phi(x,y)$ the number of strictly $y$-smooth numbers in $[2,k]$. Then there is a formula for the number of equal pairs in the table up to $k$ each way.

$$(k-1)^2 P_=(k) = \sum_{p \le k} \Phi(k, p)^2$$

where the sum is over all primes $p$ up to $k$. For example, with $k=8$, the sum is $3^2 + 2^2 + 1^2 + 1^2 = 15$, and $\frac12 (1 - \frac{15}{49}) = \frac{17}{49}$, as you calculated.

But clearly there are no more than $\pi(k)$ terms in this sum, and the biggest term is $\log_2(k)^2$, so we have a value for the probability of approximately

$$P_=(k) = \frac{1}{(k-1)^2} \frac{k}{\log k} \log_2(k)^2 \sim \frac{\log k}{k} \to 0$$