I propose a methodology to help find large prime numbers with a much higher probability than picking up random numbers and testing them for primality. This would help speed up prime number generators based on primality tests, by reducing the number of integers needed to be checked to get one prime.
Most sequences of interest, say $n^2+n+41$ or the Mersenne sequence $M_n$, are univariate and rely on one parameter: the iteration $n$. Here we are dealing with bivariate sequences, visiting them diagonally rather then horizontally or vertically.
My questions are:
- Is my methodology sound?
- Are there any better sequences?
- Is my definition of power (see below) sound, is it a new concept?
Definitions and example
The prime power $\pi_n$ of a sequence measures its ability to generate prime numbers. It is an asymptotic metric measuring the empirical probability that the $n$-th term in the sequence is a prime number, and allowing you to compare two sequences to decide which one works best.
Let's start with a classic, well studied example to illustrate the concept: arithmetic progressions. For a fixed integer $k$, the sequence $f_k(x)=k!\cdot x+1$ with $x=0, 1, 2, 3\dots$ is an arithmetic progression with $\gcd(k!, 1)=1$ and thus contains infinitely many primes. The density of primes in that sequence depends on the parameter $k$. More precisely, the number of prime numbers among $f_k(0), \cdots,f_k(n)$ as $n\rightarrow\infty$ is asymptotically
$$\rho_n(k) \sim \frac{k!}{\phi(k!)}\cdot \frac{n}{\log n}$$
where $\phi$ is Euler's Totient function. This result can easily be derived from the Prime Number Theorem for arithmetic progressions. Thus, the empirical probability for $f_k(n)$ to be prime if $k$ is fixed, that is the power of the sequence, is
$$\pi_n(k) = \frac{k!}{\phi(k!)}\cdot \frac{1}{\log n}.$$
The worst case, resulting in the lowest probability $\pi_n(k)$, is when $k=1$. Then the sequence consists of all strictly positive integers. The larger $k$, the higher the probability that the $n$-th term is a prime. Not only that, but in addition the sequence grows faster and thus generates more prime numbers, and bigger ones. With $k=13$ we have $5.21$ times more prime numbers among the first $n$ terms (when $n$ becomes large) and the $k$-term is $k!$ times larger than with $k=1$. Yet, primes become rarer and rarer as $n$ increases.
Note: We have $k! /\phi(k!) \sim e^{\gamma} \log\log k! \rightarrow \infty$ where $\gamma=0.57721\dots$ is the Euler-Mascheroni constant. To prove this important result, first note that $\log k! =k \log k - k +O(\log k)$, thus $\log\log k! =\log k + O(\log\log k)$. Then use the fact that
$$\phi(k!) =k! \prod_{p\leq k}\Big(1-\frac{1}{p}\Big) \sim \frac{e^{-\gamma}}{\log k}$$ where the product is over all primes $\leq k$. This means that as $k$ grows, the density of primes in the sequence $k!\cdot x+1$ (with $k$ fixed and $x=1,2,\dots$) becomes infinitely higher than the density of primes in the sequence of positive integers (that is, with $k=1$). This is the best that can be achieved with arithmetic progressions, see here why.
The prime booster
Since the sequences $f_k(x)$, for $k$ fixed, have more prime power as $k$ grows, the idea is to make $k$ depends on $x$ or the other way around. For instance, the new following sequence is based on this principle, using $x=k!$:
$$g_k = (k!)^2 +1.$$
It has less prime power than the sequence $k! +1$, but this is compensated by the fact that the primes it generates become very quickly extremely large. Still, $g_k$ is prime for
$$k=1, 2, 3, 4, 5, 9, 10, 11, 13, 24,\cdots$$
and maybe for some or all of $k=41, 55, 61, 73, 75, 80, 89$. The tool I used (see here) to determine the primality status for the latter $g_k$'s takes too long to provide an answer: $g_{89}=(89!)^2+1$ has $273$ digits, yet its probability to be prime would be $(\log g_{89})^{-1} =0.16\%$ if it was a random number. Of course, it is not any arbitrary number, thus its probability to be prime is much, much higher.
Now we assume that there is no congruential artifact such as (for instance) $(k!)^2+1$ never being a prime. Obviously, this is not the case here, but if it was, we would need to randomize $(k!)^2$ and replace with (say) a Poisson deviate of expectation $(k!)^2$ and variance $(k!)^2$. Also, we should avoid sequences growing too fast, such as $g_k = (k!)^{k(k+1)}+1$. The total expected number of primes to be found as $k \rightarrow\infty$ is the sum of the inverse of $\log g_k$, if the terms in the sequence were random: you want it to converge as fast as possible to $\infty$. If that series converges to a finite value because $g_k$ grows too fast, you may end up with only a finite number of primes due to pure probabilistic reasons, not because of congruential issues (or maybe both).
Another type of sequence, with better prime power, is the following one:
- Slice 1. The first $n_1$ terms are $1!\cdot x+1$, with $x=1,\dots,n_1$.
- Slice 2. The next $n_2$ terms are $2!\cdot x+1$, with $x=1,\dots,n_2$.
- Slice 3. The next $n_3$ terms are $3!\cdot x+1$, with $x=1,\dots,n_3$.
- Slice 4. The next $n_4$ terms are $4!\cdot x+1$, with $x=1,\dots,n_4$.
- And so on.
If $n_k \approx (k \log \log k)/\log k$, expect to get one prime in each slice on average. Or you may exit a slice once you have found a prime, and then move to the next slice. If $n_k=12$ is a constant, the first 459 terms in the sequence (after removing a few duplicates at the beginning) contain 93 primes, the largest of which is 2447745849743693203036833808788347682816000000001. By contrast, among the first 459 strictly positive integers, we have 88 primes, the largest of which being 457.
Now if the goal is to obtain a large prime very fast, it's difficult to beat this: compute $60! \cdot x + 1$ for $x=1,2,\dots$. It turns out that $x=6$ yields the prime
49925922676448340865658047099340186284525035638167475714695666178457600000000000001
with 82 digits. With $80!\cdot x + 1$, the first prime candidates are for $x=4, 6, 20$. For $x=29$, we get a confirmed prime with 121 digits:
2075514254341650266549534477972409432801955062928606824736173906688584138408924316437399401151143608320000000000000000001
Note that the sequences involving $k!\cdot x+1$ are not only non congruentially equidistributed, but even the sub-sequences consisting of their primes only are not: $\bmod(k!\cdot x+1, p) = 1$ regardless of the prime $p$, when $k \geq p$, and regardless as to whether or not $k!\cdot x+1$ is prime.
Second example
I am still working on it, but it is based on the convergents of the continued fraction $[1; x, x^2,x^3,\dots]$. More specifically, here $f_k(x)=P_k(x)-Q_k(x)-x^{(k-1)(k+2)/2}$. The functions $P_k(x)$ and $Q_k(x)$ are the $k$-th numerator and denominator of the continuted fraction, with the difference well approximated by $x^{(k-1)(k+2)/2}$, see here. For any fixed $k$, the sequence $f_k(x)$ grows very fast, much faster than $k^k$ or $k!$. There is a decent amount of large primes (see here), and you can get many more by removing all powers of $2, 3$ and $5$ from the composite terms if you can do the divisions efficiently (see here). Many terms tend to have very small factors, and thus they can be skipped easily without an expensive primality test.
This set of sequences has strange congruential properties. For $k=9$ for instance, we have the following. If $\bmod(x, 3)=4$ or $\bmod(x, 5)=12$, then $f_k(x)$ is not a prime. If $x=6, 23, 39, 45, 50, 56, 78, 83, 89, 105,\dots$ then $f_k(x)$ is a multiple of $11$. The gaps between these values of $x$ are $17, 16, 6, 5, 6, 22, 5, 6, 16,\dots$ and exhibit periodicity. They are displayed in the chart below. These facts can be used to skip terms in the sequence that are known not to be prime.
The initial conditions attached to the second order recurrence used to compute $P_x(x)$ and $Q_k(x)$ (see here) are
$$ \begin{equation*} \begin{pmatrix} P_{-2} & P_{-1} \\ Q_{-2} & Q_{-1} \\ \end{pmatrix} = \begin{pmatrix} 0 & 1 \\ 1 & 0 \\ \end{pmatrix} \end{equation*} $$ Note that the determinant of the above matrix is $\pm 1$. This is always the case for continued fractions. It would be interesting to see what happens if we choose different initial conditions, with a determinant also equal to $\pm 1$.
