# Pick random integer between $2$ and $100$, expected value of the number of primes that divide $n$?

Sally picks a random integer $$n$$ between $$2$$ and $$100$$. What is the expected value of the number of primes that divide $$n$$?

I think the answer is$$\sum_{\text{primes }p \text{ where }2 \le p \le 97} {{\text{# of those divisible by }p\text{ from }2\text{ to }100 \text{ (inclusive)}}\over{99}}$$Computing the first few terms, I get$${50\over{99}} + {{33}\over{99}} + {{20}\over{99}} + {{14}\over{99}} + \ldots$$ However, I'm lazy and I'm wondering if there is a quicker way to finish solving this problem without having to calculate every single last term and add them all up.

• Do you pick with or without replacement? Jul 27 '21 at 12:27
• Note that $\left\lfloor\frac{100}{2}\right\rfloor = 50$, $\left\lfloor\frac{100}{3}\right\rfloor = 33$, $\left\lfloor\frac{100}{5}\right\rfloor = 20$ and so on. I don't know how you were calculating $50,33,20,14,\dots$ but it shouldn't take too long. Once you get to the primes between $33$ and $50$ those contribute $2$, once you get to the primes $51$ to $99$ those contribute $1$. Jul 27 '21 at 12:34
• As for writing this as a sum like you had, that is absolutely correct and follows from the linearity of expectation. Jul 27 '21 at 12:34
• It looks like it can be approximated by $\frac{100}{99}\sum\frac1p\approx\frac{100}{99}\ln(\ln(101))$ Jul 27 '21 at 12:37
• wolfram calculation Jul 27 '21 at 12:41

The primes $$2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97$$ ($$25$$ of) of them have one prime factor. But so do the powers of primes. $$4,8,16,32,64, 9, 27,81,25,49$$ so $$10$$ of those so there are $$35$$ numbers with one prime factor.

If we take those with $$1$$ prime factors and multiply by a prime that isn't a factor to get a number with $$2$$ prime factors we get.

$$2 \times 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 9,27,25,49$$ are $$18$$ such numbers. (Tally $$18$$ number with 2 prime factors. $$53$$ numbers total.)

$$4\times 3, 5, 7, 11, 13, 17, 19, 23,9, 25$$ are $$10$$ such numbers.($$28$$ with 2 factors. $$63$$ total)

$$8\times 3,5,7,11,9$$ are $$5$$ such numbers.($$33$$, $68). $$16\times 3,5$$ are $$2$$ such numbers. ($$35,70$$) $$32\times 3$$ is $$1$$.($$36,71$$) $$3\times 7, 11, 13, 17, 19, 23, 29, 31,25$$ are $$9$$ such numbers.($$45,80$$) $$9\times 7,11$$ are $$2$$ such numbers. ($$47,82$$) And $$27\times 5> 10$$ so there are no more powers of $$3$$ to consider. $$5\times 3, 5, 7, 11, 13, 17, 19$$ are$$7$$ more.($$54,89$$) $$7\times 11,13$$ are the last $$2$$. Any more would be the product of $$2$$ primes over $$10$$.($$56,91$$) So there are $$56$$ numbers with $$2$$ factors. That accounts for $$91$$ of the $$99$$ numbers. There are only $$8$$ with $$3$$ or more factors. They are $$2\times 3\times 5, 4\times 3\times 5, 2\times 9\times 5,2\times 3\times 7, 4\times 3\times 7, 2\times 3\times 11,2\times 3\times 13,2\times 5\times 7$$ And so there are $$35 + 2\times 56 + 3\times 8 = 171$$ prime factors spread among $$99$$ numbers. The expected value of the number of prime factors of $$n$$ is $$\frac {171}{99}$$. • Argh... spent to long working on that. Keith Backman did the same thing but didn't waste time calculating the just majority of those with$2\$ primes. Jul 27 '21 at 17:48

There are $$25$$ primes smaller than $$100$$. In addition, there are $$10$$ numbers that are powers of primes smaller than $$100$$: $$4,8,9,16,25,27,32,49,64,81$$. In total, there are $$35$$ numbers between $$2$$ and $$100$$ inclusive that have only one prime factor.

Since $$2\cdot 3\cdot 5\cdot7=210>100$$, there are no numbers in that range which have four or more prime factors. There are $$8$$ numbers in that range which have three prime factors: $$30,42,60,66,70,78,84,90$$. You can either count those which have two prime factors, or calculate that number as $$99-35-8=56$$.

A randomly chosen number has $$\frac{35}{99}$$ chance of having $$1$$ prime factor, $$\frac{56}{99}$$ chance of having $$2$$ prime factors, and $$\frac{8}{99}$$ chance of having $$3$$ prime factors.

The expected number of prime factors would be $$1\cdot\frac{35}{99}+2\cdot\frac{56}{99}+3\cdot\frac{8}{99}=\frac{171}{99}$$, or between $$1$$ and $$2$$, with a slight bias towards $$2$$.