7
$\begingroup$

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

  • 0
    Thanks, Gerry, those are new to me! Here's [a PDF download link](http://www.math.kth.se/~rikardo/beurling.pdf) to "Properties of the Beurling generalized primes."2012-07-25

3 Answers 3

1

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

4

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

  • 0
    So that means my method might be useful?2012-07-25
3

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.