# Probability question with application to number theory and cryptography

See below $$12$$ integers that were produced with a very special sequence, related to the convergents of the infinite continued fraction $$[1;x,x^2,x^3\cdots]$$. It seems to very quickly produce a good volume of large prime numbers. My question here is about some probability distribution and how likely it is to produce such numbers just by pure chance, as opposed to having a mechanism substantially favoring prime numbers.

q[1]=1894781600065430642191487501
q[2]=168790857865466969963095825949163521
q[3]=16628493352040780085201985147225608409
q[4]=41487650955090529024111541483994577947443
q[5]=502591166807658411397925920157836801828437089
q[6]=7404463607964940201325616032545655701765368751
q[7]=9056704270394224151095119334673760092485217895841
q[8]=551133648009096489422941271373285130650625283200001
q[9]=3694353145828504603260875625147011592990036756912253
q[10]=674517257387347108840745520305846961596848815453339649
q[11]=15296902337973981607460855404070187211986806704724902433
q[12]=1081530142405334900540794715710550544143142264486339447029


The numbers $$q_5,q_6,q_7,q_{12}$$ have divisors smaller than $$1000$$ and the remaining eight numbers have no divisor smaller than $$N=15485863$$. Note that $$N$$ (the one-millionth prime) is the largest divisor that I tried. I suspect that the eight numbers with no small divisor are all prime. Of course if you can use a fast primality test to answer that question directly, that's great. Here however, I tried to assess the chances of observing various events linked to these numbers, using probabilistic arguments.

The probability for a large number $$x$$ to be prime is about $$1 / \log x$$, by virtue of the Prime Number Theorem. The probability for a large number $$x$$ to have no divisor smaller than $$N$$ is

$$\rho_N=\prod_{p

where the product is over all primes $$p and $$\gamma=0.577215\dots$$ is the Euler–Mascheroni constant. See here for an explanation. Here $$\rho_N\approx 0.033913$$. Of course, the probability to observe $$4$$ large numbers out of $$12$$ having no divisor smaller than $$N$$ is $${{12}\choose{8}} \rho_N^8 (1-\rho_N)^4 \approx 7.54512 \times 10^{-10}$$ Also, the probability for $$x$$ to be prime if it has no divisor smaller than $$N$$ is equal to $$P(x \mbox{ prime } | x \mbox{ has no divisor } < N)= \frac{P(x \mbox{ prime})}{P(x \mbox{ has no divisor } < N)}=\frac{1}{\rho_N\log x}.$$

It turns out that for the numbers $$q_1,\cdots,q_{12}$$, the probability in question is not small at all. For instance, equal to $$0.47, 0.36, 0.23$$ respectively for $$q_1,q_2, q_{11}$$. But what I am interested in here is the probability that no more than $$4$$ out of $$12$$ large numbers are actually non-prime. We would be dealing with a binomial distribution if the parameters $$p_k=P(q_k \mbox{ prime})$$ were identical for $$k=1,\cdots,12$$ but in reality they are not: $$p_k = 1/\log q_k$$. So we are dealing with a sum of $$12$$ independent but non-identically distributed Bernouilli variables of parameter $$p_1,\cdots,p_{12}$$. For instance the probability that exactly two numbers are non-prime is very simple, it is equal to

$$\Big(\prod_{k=1}^{12} p_k\Big)\sum_{1\leq i

My question here is to identify that distribution and compute the probability in question for my example. It's easy to find its characteristic function (CF), but inverting the CF to obtain the density seems tricky. Maybe finding the moments is much easier: the first one (expectation) is of course $$p_1+\cdots p_{12}$$. See also here. Note that we assumed here that the events "$$q_k$$ is prime" for $$k=1,\cdots,12$$ are independent. Prime numbers indeed exhibit a good amount of randomness, but the very purpose of my project is to identify deterministic holes or failures in that randomness, to be able to generate large primes, thus the spectacular probabilities obtained here, that defeat true randomness.

• "The probability for a large number x to be prime is about 1/logx, by virtue of the Prime Number Theorem." No. The probability that an integer chosen at random from [1,x] will be prime is 1/log x. Source = en.wikipedia.org/wiki/Prime_number_theorem. Commented Oct 14, 2020 at 2:56
• The CDF is $F(x) = \log x$, that's the number of primes less than $x$. Thus the density at $x$ (or probability since we are dealing with a discrete distribution) is $f(x) = F(x) - F(x-1)$. Let me think about this, because the $1/\log x$ I came up with is not from me, I've seen it mentioned a few time, though it does not mean it's correct. Commented Oct 14, 2020 at 3:27
• Ironic, I am also having second thoughts, and am working on this. The approach that I am considering is how much more likely is that a number chosen at random from [1,n] will be prime than a number chosen at random from [1,2n]. Then I am wondering what happens to this distinction as $n \to \infty$. Calculation in progress. Commented Oct 14, 2020 at 3:30
• Re my last two notes, I now suspect that the assertion in your query is correct. Re my last note, contrast $\frac{1}{\log n}$ with $\frac{1}{\log (2n)} = \frac{1}{\log n + \log 2}.$ As $n \to \infty$, the $\log 2$ in the denominator becomes trivial. This means that as $n \to \infty$, the fact that the primes are moderately bottom heavy becomes less and less important. Therefore, I do suspect, without being sure, that as $n \to \infty$, considerations of bottom heaviness become irrelevant. Commented Oct 14, 2020 at 3:34
• For what it's worth, alpertron.com.ar/ECM.HTM takes 0.2 seconds to factor all of these numbers. Only q[3] and q[9] are actually prime. Commented Oct 17, 2020 at 19:49

Let $$X$$ be the number of large numbers that are prime among $$q_1,\cdots,q_n$$ with $$n=12$$. Then $$X$$ has a Poisson Binomial distribution: $$X$$ is the sum of $$n$$ independent Bernouilli variables of parameters $$p_k=1/\log q_k$$ for $$k=1,\cdots,n$$. The first moments are
$$\mbox{E}(X)=\sum_{k=1}^n p_k,\\ \mbox{Var}(X)=\sum_{k=1}^n p_k (1-p_k).$$
Since the $$p_k$$'s are very small, we can use the Poisson approximation, see Le Cam's theorem. Let $$\lambda=p_1+\cdots+p_n$$. Then for $$m=0,\cdots,n$$, we have $$P(X=m)\approx \frac{\lambda^m e^{-\lambda}}{m!}.$$ In our example, the computation is as follow. First compute the $$p_k$$'s:
Then $$\lambda=0.11920$$. Now we can compute $$P(X=m)$$ for $$m=8,9,10,11,12$$:
The final result is the probability that $$8$$ or more large numbers are prime among $$q_1,\cdots,q_{12}$$. This is the sum of the $$5$$ probabilities in the above table. It is equal to $$9.1068 \times 10^{-13}$$.