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

$\endgroup$
12
  • $\begingroup$ What about the set $\{\Bbb{P}+n\}$? $\endgroup$
    – draks ...
    Commented Jul 24, 2012 at 12:03
  • $\begingroup$ @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... $\endgroup$ Commented Jul 24, 2012 at 12:28
  • $\begingroup$ @JosephO'Rourke This may sound trivial, what about $\lfloor \frac{n}{\log n}\rfloor$? look's nice... $\endgroup$
    – draks ...
    Commented Jul 24, 2012 at 12:40
  • $\begingroup$ @draks: Clever! But I would like to generate many random sets, not just one. $\endgroup$ Commented Jul 24, 2012 at 12:49
  • 1
    $\begingroup$ Then pick numbers $a$ and $b$, and use $$\left[{n+a\over b+\log n}\right]$$ $\endgroup$ Commented Jul 24, 2012 at 12:54

4 Answers 4

4
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Beautiful idea! How clear is it, though, that this method does arrive at the same statistical distribution? $\endgroup$ Commented Jul 24, 2012 at 18:13
  • $\begingroup$ 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. $\endgroup$
    – Old John
    Commented Jul 24, 2012 at 18:15
  • $\begingroup$ It's not hard to see that the statistical distribution will be the same with probability 1... $\endgroup$
    – Xoff
    Commented Jul 25, 2012 at 18:54
  • $\begingroup$ So that means my method might be useful? $\endgroup$
    – Old John
    Commented Jul 25, 2012 at 19:12
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
1
$\begingroup$

I’d suggest this: A number n < 210 is a pseudo prime iff n is prime. n >= 210 is not a pseudo prime if n is divisible by 2, 3, 5 or 7. If n >= 210 is not divisible by 2, 3, 5 or 7 then it is a pseudo prime with probability 210 / (48 ln n).

You might try to calculate the probability that every even n >= 4 is the sum of two pseudo primes.

$\endgroup$
1
  • $\begingroup$ This seems like an unnecessary complication for OP's purposes. Admittedly these are not very specific, but the OP seems to be only concerned with density in intervals, rather than any local behavior. $\endgroup$
    – Erick Wong
    Commented May 11 at 21:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .