1
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ Do you pick with or without replacement? $\endgroup$ Jul 27 '21 at 12:27
  • $\begingroup$ 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$. $\endgroup$
    – JMoravitz
    Jul 27 '21 at 12:34
  • $\begingroup$ As for writing this as a sum like you had, that is absolutely correct and follows from the linearity of expectation. $\endgroup$
    – JMoravitz
    Jul 27 '21 at 12:34
  • $\begingroup$ It looks like it can be approximated by $\frac{100}{99}\sum\frac1p\approx\frac{100}{99}\ln(\ln(101))$ $\endgroup$
    – Moko19
    Jul 27 '21 at 12:37
  • $\begingroup$ wolfram calculation $\endgroup$
    – JMoravitz
    Jul 27 '21 at 12:41
1
$\begingroup$

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}$.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – fleablood
    Jul 27 '21 at 17:48
1
$\begingroup$

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$.

$\endgroup$

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.