Of the first $N$ natural numbers, we select two different numbers at random. We'll call the greater one $A$ and the lesser one $B$. What is the probability $P$ that the sum of $A$'s prime factors is less than the sum of $B$'s prime factors?

For instance, if $A = 20$ and $B = 11$, $A$'s prime factors are $2$, $2$, and $5$ (sum $= 9$), and $B$'s prime factors are $11$ (sum $= 11$). So this satisfies the condition that $A > B$ (as $20 > 11$), but the sum of prime factors of $A$ is less than the sum of prime factors of $B$ (as $9 < 11$).

I presume that this question or something near it has been answered before, but I suck at searching through mathematics literature. So I just arduously calculated this probability for $N = 2$ through $300$. When $N = 10$, the probability's about $4.4\%$, but it slowly moves upward to:

$10\%$ at $N = 20$; $19.2\%$ at $N = 50$; $24.5\%$ at $N = 100$; $28.2\%$ at $N = 200$; $30.1\%$ at $N = 300$. (I can provide more complete data if necessary.)

The growth seems to slow logarithmically (prime number theorem hunch), so I did some division. And for some reason, $\ln N/P$ tends toward somewhere around $19.04$, with little oscillation once $N$ is above $100$.

My question: anyone know why? Why $19.04$?

  • $\begingroup$ The number of distinct prime factors is very well known from a statistics viewpoint, that is the Erdos-Kac theorem. Less precision on number of divisors or sum of divisors( See Hardy and Wright). Not aware of anything compelling on sum of distinct prime divisors. $\endgroup$ – Will Jagy Jul 29 '14 at 4:10
  • 2
    $\begingroup$ Doesn't the ratio $19.04$ have to change at some point? After all, $P \leq 1$. $\endgroup$ – Brian Tung Jun 6 '15 at 4:37
  • $\begingroup$ @BrianTung:. Indeed it has to, and it does. For example for $N=500,1000,2000,5000,10000,20000$ the probabilities are about $ 0.3216, 0.3435, 0.3612, 0.3801, 0.3908, 0.3999$ and the ratios are about $19.32, 20.11, 21.04, 22.41, 23.57, 24.77$. It wouldn't surprise me if the probability approached $0.5$. $\endgroup$ – Henry Jun 13 '15 at 20:43

Your Answer

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

Browse other questions tagged or ask your own question.