Suppose we have a given integer $n$. We randomly pick an integer $k$, where $k\leq n$. Then What is the probability that $k$ divides $n$?
$\begingroup$
$\endgroup$
5
-
2$\begingroup$ Very small. It is technically d(n) ,the number of divisors of n, divided by n. The quantity d(n) varies from (for n > 1) 2 to log base 2 of n. How d(n) varies over a range has been studied, in general the number is about log(log(n)), and the literature tells you how it varies from this. Sometimes $\tau$ is used instead of d for this function. Gerhard "Check Out The Chances Online" Paseman, 2015.09.25 $\endgroup$– Gerhard PasemanSep 26, 2015 at 1:05
-
$\begingroup$ Hmm. The average of the d(i) for i from 1 to n is larger than I expected. I will need to check what is counted by log(log(n)). Gerhard "Odds Bigger Than I Thought" Paseman, 2015.09.25 $\endgroup$– Gerhard PasemanSep 26, 2015 at 1:19
-
$\begingroup$ @GerhardPaseman, the number of prime divisors. en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Kac_theorem $\endgroup$– Will JagySep 26, 2015 at 1:47
-
1$\begingroup$ Thanks Will. I've temporarily lost the capacity to distinguish between $\omega$ and d. Gerhard "Hopefully It Will Come Back" Paseman, 2015.09.25 $\endgroup$– Gerhard PasemanSep 26, 2015 at 1:50
-
$\begingroup$ If you allow negative $k$, this greatly reduces the changes. $\endgroup$– joroSep 26, 2015 at 7:38
Add a comment
|