Phase transition in a stochastic prime-number generator

We introduce a stochastic algorithm that acts as a prime-number generator. The dynamics of this algorithm gives rise to a continuous phase transition, which separates a phase where the algorithm is able to reduce a whole set of integers into primes and a phase where the system reaches a frozen state with low prime density. We present both numerical simulations and an analytical approach in terms of an annealed approximation, by means of which the data are collapsed. A critical slowing-down phenomenon is also outlined.

Figure 1

Ratio $r$ of prime numbers in the steady state as a function of $N$ for different pool sizes $M$. Each point is the average of $2\times {10}^4$ realizations. For small values of $N$, the value of $r$ is only related to the amount expected from a random sample. For large values of $N$, $r$ tends to 1: the algorithm is able to reduce the whole system to primes.

Figure 2

Order parameter $P$, defined as the probability that all numbers are prime in the steady state, versus the control parameter $N$, for the same pool sizes as for Fig. 1 (simulations are averaged over $2\times {10}^4$ realizations). Inset: scaling of $N_c$ versus $M∕\ln \left(M\right)$, for pool sizes $M=2^{10},2^{11},\dots ,2^{17}$.

Figure 3

Probability $1-q(N,M)$ that at least two numbers from $N$ be exactly divisible one into the other, for different values of $M$ (from left to right, $2^{13},2^{14},2^{15},2^{16}$, and $2^{17}$). Each point represents the average of ${10}^5$ realizations. Inset: Scaling, in the annealed system, of $N_c$ (defined such that $q(N_c,M)=0.5$) versus $M∕\ln \left(M\right)$ for different values of $M=2^{11},2^{12},\dots ,2^{17}$.

Figure 4

Collapse of the order parameter $P$ for different values of $M=2^{14},2^{15},2^{16},2^{17}$, with $\alpha =0.59$.

Figure 5

Characteristic time $\tau$ as defined in the text versus $N$, for different pool sizes, from left to right, $M=2^{10},2^{11},2^{12},2^{13},2^{14}$. Every simulation is averaged over $2\times {10}^4$ realizations. Note that, for each curve, $\tau (N,M)$ reaches a maximum in a neighborhood $N_c\left(M\right)$.