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
    What about the set $\{\Bbb{P}+n\}$?2012-07-24
  • 0
    @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...2012-07-24
  • 0
    @JosephO'Rourke This may sound trivial, what about $\lfloor \frac{n}{\log n}\rfloor$? [look's nice](http://tinyurl.com/cfd3mck)...2012-07-24
  • 0
    @draks: Clever! But I would like to generate many random sets, not just one.2012-07-24
  • 1
    Then pick numbers $a$ and $b$, and use $$\left[{n+a\over b+\log n}\right]$$2012-07-24
  • 0
    @JosephO'Rourke ... or if it's (matlab) programming add k*randn(1) or friends.2012-07-24
  • 0
    @JosephO'Rourke I'm curious: What do you think about Gerry's randomization?2012-07-25
  • 0
    @draks: I don't yet have time to implement Gerry's suggestion. I worry about the choice of $\lbrace a,b \rbrace$...2012-07-25
  • 0
    @Gerry How to pick $a$ and $b$, such that Joseph doesn't worry anymore?2012-07-25
  • 0
    @draks, I don't think it matters much. Whatever $a,b$ you use, you get the right asymptotics. I suppose there is the problem of wanting different sets to be very different. Maybe it would be better to use $$\left[{n+n^a\over\log n}\right]$$ for various values of $a$, $0\le a\lt1$.2012-07-25
  • 0
    By the way, you might be interested in the "Beurling generalized primes".2012-07-25
  • 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
    Beautiful idea! How clear is it, though, that this method does arrive at the same statistical distribution?2012-07-24
  • 0
    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.2012-07-24
  • 0
    It's not hard to see that the statistical distribution will be the same with probability 1...2012-07-25
  • 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.