Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Imagine a set $S$ of $10^{12}$ consecutive integers $n, n + 1, n + 2, n + 3, \ldots, n + 10^{12}-1$, where the exact identity of $n$ will be partially determined randomly as described below, and otherwise left unspecified.

First we decide whether $n$ is divisible by $2$, with probability $1/2$ for each possibility. That determines which members of $S$ are even and which are odd. Among those that are even, we toss another coin to decide which are divisible by $2^2$, then similarly for $2^3$, etc. It is not quite certain that any will be divisible by $2^{40}$, since that's a bit bigger than $10^{12}$, and there's a probability a bit less than $1/2$ that at least one will be divisible by $2^{41}$, etc.

Then we do likewise with $3$, then with $5$, and so on through the list of all primes.

There is a certain probability that a number will not be thus identified as divisible by any prime. This will be, in effect, a prime number but not any particular prime number, just as $n$ is not any particular number.

Can anyone say anything of interest about the probability distribution of the number of such mystery primes, or the probability distributions of their locations? Will they be the same as if we let the value of $n$ be an actual number and then found limits of these probabilities as $n\to\infty$?

Later edit: Henry's answer called to my attention what I should have thought of before: the expected number of primes by which $n$ is divisible would be $1/2 + 1/3 + 1/5 + 1/7 + 1/11 + \cdots$, so $n$ would be infinite. And none of the numbers in this interval of length $10^{12}$ would be prime.

This is a different kind of infinite number from those I've thought about before. But it's a perfectly tractable one: one could examine its properties.

This seems rather unlike the infinite integers of nonstandard analysis, because with each of those one can say that there is some larger infinite integer that is prime. It's not so clear how that would make sense with something like this. But yet it's quite similar to the infinite integers of nonstandard analysis in some ways: every third one is divisible by 3, every ninth one by $3^2$, etc.

Another comment: Actually, in one sense they're not so different from the infinite integers of nonstandard analysis. Almost all of them have infinitely many distinct prime factors. One difference is that with those infinite integers, each has a largest prime factor, which is infinitely large. And although one can say that for each infinite integer $n$, there is a prime $p$ greater than $n$, in almost every case its difference from $n$ will not be finite.

share|cite|improve this question
There is a certain amount of vagueness in the question. Rather than resolving it, I'm going to let it be considered part of the question to say how it ought to get resolved, if at all. – Michael Hardy Oct 20 '11 at 22:53
Are you familiar with the Hawkins random sieve? It seems fairly close to what you are describing, though not exactly. – Unreasonable Sin Oct 20 '11 at 22:57
I'm looking forward to your next question: "Pick a random number of random numbers, and do a random number of random things to them: anybody know what will happen?" – Gerry Myerson Oct 20 '11 at 23:51
@Gerry: Actually, I was quite specific as to what one is to do. – Michael Hardy Oct 21 '11 at 2:31
@Michael: I don't know whether I got your question (and intention) correctly. But I'm just looking at an old exercise on asymptotic density of primefactors, and the expression I use (partial Eulerproducts) may or may not be another view useful at least for the intention of your question (I also don't know anything about nonstandard analysis). If you want to take a look, here is a current table: .Perhaps you can make something useful out of it. – Gottfried Helms Oct 22 '11 at 14:48
up vote 5 down vote accepted

With probability one, your mystery number $n$ will be divisible by an infinite number of primes, i.e. it will be infinite.

Here is a related random process where you might think the probability of a mystery number not being divisible by a prime was the product over all the primes of $\left(1-\dfrac{1}{p}\right)$, i.e. $\dfrac{1}{2} \times \dfrac{2}{3} \times \dfrac{4}{5} \times \dfrac{6}{7} \times \dfrac{10}{11} \times \cdots$. The limit of this is $0$.

Perhaps that is a little unfair. Instead look at the partial product over primes which are less than or equal to $\sqrt{n}$. Then you will find that the partial product is not that far away from $1/\log_e (n)$ (for $n \ge 80$ it is slightly more). And that is an interesting result.

share|cite|improve this answer
You're right: I should have thought this through before posting. The expected number of primes by which $n$ is divisible is $1/2 + 1/3 + 1/5 + 1/7 + 1/11 + \cdots$. Given the way I stated the problem, it doesn't make sense to speak of a square root of $n$. Or of $\log_e n$. $n$ would have to be a particular finite number in order for that to be possible. – Michael Hardy Oct 21 '11 at 2:38

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.