Take the 2-minute tour ×
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.

I would like to generate random numbers whose distribution mimics that of the primes. So the number of generated random numbers less than $n$ should grow like $n / \log n$, most intervals $[n,n+n^\epsilon]$ should contain approximately $n^\epsilon / \log n$ generated numbers (Selberg's short intervals), etc. Does anyone know of a computationally feasible method for generating such "look-a-like primes"?

Addendum. I implemented Henry and Xoff's suggestions. Here are several instances of the first ten "pseudoprimes": $$ 4, 5, 9, 10, 17, 23, 27, 28, 31, 44 $$ $$ 7, 8, 9, 10, 12, 15, 18, 19, 27, 34 $$ $$ 6, 11, 15, 16, 23, 26, 27, 29, 45, 49 $$ And here is the cumulative distribution pseudoprimes up to $10^6$ (red), together with a plot of $n / \log n$ (purple), for one random run:
         Cumulative distribution

share|improve this question
    
What about the set $\{\Bbb{P}+n\}$? –  draks ... Jul 24 '12 at 12:03
    
@draks: Thanks for the suggestion. Yes, I thought of employing the prime distribution itself, but I would prefer not to resort to that. I am thinking more of scaling some standard distribution to match the prime distribution... –  Joseph O'Rourke Jul 24 '12 at 12:28
    
@JosephO'Rourke This may sound trivial, what about $\lfloor \frac{n}{\log n}\rfloor$? look's nice... –  draks ... Jul 24 '12 at 12:40
    
@draks: Clever! But I would like to generate many random sets, not just one. –  Joseph O'Rourke Jul 24 '12 at 12:49
1  
Then pick numbers $a$ and $b$, and use $$\left[{n+a\over b+\log n}\right]$$ –  Gerry Myerson Jul 24 '12 at 12:54
show 7 more comments

3 Answers

up vote 3 down vote accepted

You could generate random numbers $U_2,U_3,U_4,\ldots$ independently and uniformly in $[0,1]$ and include $n$ in your random set if $U_n \lt \dfrac{1}{\log_e n} - \dfrac{1}{2(\log_e n)^2}$ or some similar expression.

share|improve this answer
add comment

Not sure if this fits the bill, but how about the following process.

Since the (normal) primes can be generated by a sieve (sieve out all multiples of 2, then 3, then 5, etc.), how about using a similar sieving process, but choose a random offset for each run through the sieving process?

For example, first sieve out every second number starting randomly with 1 or 2.

Then sieve out all multiples of 3 starting randomly at 1, 2 or 3.

Repeat until you get to the square root of the limit you want to go up to.

Since the standard Eratosthenes sieve is pretty fast when it gets going, this might be a good process if you want a reasonable-sized block of "primes".

share|improve this answer
    
Beautiful idea! How clear is it, though, that this method does arrive at the same statistical distribution? –  Joseph O'Rourke Jul 24 '12 at 18:13
    
I am not sure about that ... and wondered if someone would ask! Maybe this could be another possible question for the site? But I suspect (after a very brief think about it) that it ought to be provable using the Chinese remainder theorem. –  Old John Jul 24 '12 at 18:15
    
It's not hard to see that the statistical distribution will be the same with probability 1... –  Xoff Jul 25 '12 at 18:54
    
So that means my method might be useful? –  Old John Jul 25 '12 at 19:12
add comment

The number 1 is in your set, then then number $n$ is in your set with probability $\frac{1}{\log(n)}$.

So for each number, you use a uniform random variable $X$ in $[0;1]$ and test if $X<\frac{1}{\log(n)}$.

share|improve this answer
add comment

Your Answer

 
discard

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.