2. Generation of Primes and Coprimes
The Hybrid Prime Factorization (HPF) algebraic structure, defined in the next section, is used to generate larger primes and coprimes. It consists of a coprime sum or difference, subject to several conditions.
2.1. The HPF Algebraic Structure
“HPF” refers to an algebraic expression of the form
$\mathrm{HPF}={\mathrm{p}}_{1}^{{\mathrm{a}}_{1}}\bullet {\mathrm{p}}_{2}^{{\mathrm{a}}_{2}}\bullet \dots \bullet \mathrm{}{\mathrm{p}}_{\mathrm{n}}^{{\mathrm{a}}_{\mathrm{n}}}\pm {\mathrm{p}}_{1}^{{\mathrm{b}}_{1}}\bullet {\mathrm{p}}_{2}^{{\mathrm{b}}_{2}}\bullet \dots \bullet \mathrm{}{\mathrm{p}}_{\mathrm{n}}^{{\mathrm{b}}_{\mathrm{n}}}\mathrm{}$(1)
where ${\mathrm{p}}_{1},{\mathrm{p}}_{2}\dots ,{\mathrm{p}}_{\mathrm{n}}$ denote the first n primes and the integer exponents ${\mathrm{a}}_{\mathrm{i}},{\mathrm{b}}_{\mathrm{i}}\mathrm{}$satisfy the conditions:
${\mathrm{a}}_{\mathrm{i}},\mathrm{}{\mathrm{b}}_{\mathrm{i}}\mathrm{}\ge 0$(2)
${\mathrm{a}}_{\mathrm{i}}\mathrm{}\bullet {\mathrm{b}}_{\mathrm{i}}=0$(3)
${\mathrm{a}}_{\mathrm{i}}+{\mathrm{b}}_{\mathrm{i}}\ge 1$(4)
$\sum _{\mathrm{i}=1}^{\mathrm{n}}{\mathrm{a}}_{\mathrm{i}}\ge 1$(5)
$\sum _{\mathrm{i}=1}^{\mathrm{n}}{\mathrm{b}}_{\mathrm{i}}\ge 1$(6)
for $\mathrm{i}=1,\mathrm{}2,\mathrm{}3,\dots ,\mathrm{n}$.
Inequalities (
2)-(
4) ensure that the two multiplicative terms in (
1) are coprime, i.e. no
${\mathrm{p}}_{\mathrm{i}}\mathrm{}$can be a factor in both terms, and (
5)-(
6) prevent either term in (
1) to be 1. Condition (
7) eliminates any trivial, non-prime solutions, i.e. where
$\mathrm{HPF}=1$, such as:
${2}^{4}-3\bullet 5$,
${5}^{2}-{2}^{3}\bullet 3$,
${2}^{2}{\bullet 3}^{2}-5\bullet 7$.
Given the HPF structure (
1)-(
7), the prime generation result reported in research
can be summarized by stating that if
$\mathrm{HPF}<{\mathrm{p}}_{\mathrm{n}+1}^{2}\mathrm{}$(8)
then the HPF represents a prime $>{\mathrm{p}}_{\mathrm{n}}$.
Example 1. Let
${\mathrm{p}}_{1}=2$,
${\mathrm{p}}_{2}=3$,
${\mathrm{p}}_{3}=5$,
${\mathrm{p}}_{4}=7$. Each of the HPF expressions below, satisfies (
2)-(
8) for
$\mathrm{n}=3$, and therefore it represents a prime
$>5$ $3\bullet 5-2=13\mathrm{}$(9)
$3\bullet 5+2=17\mathrm{}$(10)
${2}^{2}\bullet 3-5=7\mathrm{}$(11)
${2}^{2}\bullet 3+5=17\mathrm{}$(12)
${2}^{2}\bullet {3}^{2}-{5}^{2}=11.\mathrm{}$(13)
If the sufficiency conditions (
2)-(
8) are not satisfied, HPF may or may not be a prime, as shown by the expressions below:
${2}^{2}\bullet {3}^{2}+{5}^{2}=61$isprime;(
8)notsatisfied
(14) ${2}^{1}\bullet {3}^{3}-5=49$isnotprime;(
8)notsatisfied
(15) ${2}^{2}+{5}^{2}=29$isprime;(
4)notsatisfied
(16) ${2}^{6}-5=59$isprime;(
4)and(
8)notsatisfied.
(17) The result described in the above example can be generalized, based on the observation that when the HPF satisfies (
2)-(
7) but not (
8), it will either be a prime
$\ge 7$, or a composite number, coprime to {
$2,\mathrm{}3,\mathrm{}5\},\mathrm{}$with at most
$\mathrm{k}$ prime factor terms, where
$\mathrm{k}$ is the smallest integer such that
$\mathrm{HPF}<{7}^{\mathrm{k}+1}$. Hence, the prime generation result reported in research
corresponds to the special case
$\mathrm{k}=1$, for which the HPF value is predictably prime. The following proposition formalizes this generalized result.
Proposition 1. The HPF expression, given by (
1), subject to (
2)-(
4) and (
7), is:
(i) co-prime to ${\mathrm{p}}_{1},{\mathrm{p}}_{2}\dots ,{\mathrm{p}}_{\mathrm{n}}$;
(ii) $\mathrm{HPF}\ge {\mathrm{p}}_{\mathrm{n}+1}$;
(iii) the number of terms in the prime factorization of the HPF is at most $\mathrm{k}$, where $\mathrm{k}\ge 1$ is such that
$\mathrm{k}\le \frac{\mathrm{log}\left(\mathrm{HPF}\right)}{\mathrm{log}\left({\mathrm{p}}_{\mathrm{n}+1}\right)}<\mathrm{k}+1$(18)
and log(·) denotes the natural logarithm function.
Proof. The HPF, given by (
1), cannot have any of
${\mathrm{p}}_{1},{\mathrm{p}}_{2}\dots ,{\mathrm{p}}_{\mathrm{n}}$ as prime factor(s), since this would lead to a contradiction, given that the two product terms in (
1) are coprime, by virtue of conditions (
2)-(
4) and (
7). Hence, HPF > 1 is coprime to
${\mathrm{p}}_{1},{\mathrm{p}}_{2}\dots ,{\mathrm{p}}_{\mathrm{n}}$, which proves the first part of the proposition. From this, it follows that the minimum value of the HPF is
${\mathrm{p}}_{\mathrm{n}+1}$, i.e. its smallest prime factor. Therefore
$\mathrm{HPF}\ge {\mathrm{p}}_{\mathrm{n}+1}$.(19)
To prove the last part of the proposition, let $\mathrm{k}\ge 1$ such that
${\mathrm{p}}_{\mathrm{n}+1}^{\mathrm{k}}\le \mathrm{HPF}<{\mathrm{p}}_{\mathrm{n}+1}^{\mathrm{k}+1}$.(20)
Since every prime factor of HPF is
$\ge {\mathrm{p}}_{\mathrm{n}+1}$, it follows that the HPF cannot have more than k terms in its prime factorization, since this would violate the right side of (
20). By taking the natural logarithms of all sides of (
20), expression (
18) follows, and the last part of the proposition is proved.
From Proposition 1, it follows that for the special case
$\mathrm{k}=1$, the HPF, given by (
1), is a prime number in the semi-open interval [
${\mathrm{p}}_{\mathrm{n}+1},{\mathrm{p}}_{\mathrm{n}+1}^{2})$. For higher values of k, the HPF is either a prime or coprime in the semi-open interval [
${\mathrm{p}}_{\mathrm{n}+1}^{\mathrm{k}},{\mathrm{p}}_{\mathrm{n}+1}^{\mathrm{k}+1})$, with a maximum “prime factor cardinality” of k, i.e. having at most k terms in its prime factorization (including any repeating primes).
The following examples show how Proposition 1 can be used to represent, and thus generate, primes and coprimes.
Example 2. Let
$\mathrm{n}=3$ and consider the HPF expression (
15) of the previous example. In this case,
$\mathrm{k}=2$, since
$\mathrm{HPF}={2}^{1}\bullet {3}^{3}-5=49=\mathrm{}{\mathrm{p}}_{4}^{2}$(21)
and HPF is coprime to $\{2,\mathrm{}3,\mathrm{}5\}$, with a maximum prime factor cardinality of 2 and no prime factor smaller than 7.
Example 3. Consider the HPF expression ($\mathrm{n}=3$), given by
$\mathrm{HPF}={2}^{10}\bullet {3}^{5}\bullet {5}^{5}+1=777,600,001$(22)
for which, the corresponding value of k, from (
18), is
$\mathrm{k}=\u230a\frac{\mathrm{log}\left(\mathrm{HPF}\right)}{\mathrm{log}\left({\mathrm{p}}_{4}\right)}\u230b=\u230a\frac{\mathrm{log}\left(777,600,001\right)}{\mathrm{log}\left(7\right)}\u230b=10$(23)
where
$\u230a\bullet \u230b$ denotes the integer part operator. The above equation implies that (
22) has a maximum prime factor cardinality of 10, with no prime factor < 7. This is confirmed by the prime factorization of the HPF, given by
$\mathrm{HPF}=777,600,001=31\bullet 61\bullet 411,211$.(24)
The value of the HPF expression (
1) may be minimized with respect to the exponents
${\mathrm{a}}_{\mathrm{i}},\mathrm{}{\mathrm{b}}_{\mathrm{i}}$, subject to the conditions of Proposition 1, to maximize the likelihood of the HPF representing a relatively smaller prime
$>{\mathrm{p}}_{\mathrm{n}}$, or a (composite) coprime
$>{\mathrm{p}}_{\mathrm{n}}$ with relatively small prime factors and cardinality.
In general, (
1) may be viewed as an algebraic generator of primes and coprimes. Its prime and coprime generating performance is analyzed in Section 3.
2.2. Evolutional Characteristics of Primality
The algebraic system described by (
1)-(
4) and (
7) lends itself to a hierarchical evolutionary structure in the generation of primes from smaller ones. The relaxation of conditions (
5)-(
6) implies that such hierarchical generation can be traced to the smallest possible prime. To show this, consider
$\mathrm{a}$, where
$\mathrm{a}=1+1$. Since
$1<\mathrm{a}<4$, with 4 being the smallest possible non-prime (composite) number, it follows that 2 and 3 are prime. The primality of 3 may also be established from the primality of
$\mathrm{HPF}={2}^{2}-1$, since it represents a number
$>2$ and
$<4$.
The primality of
$\mathrm{HPF}={2}^{2}+1$ and
$\mathrm{HPF}={2}^{3}-1$ also follows directly from that of 2, i.e. without relying on the primality of
${\mathrm{p}}_{2}=3$. Since
$\mathrm{HPF}={2}^{\mathrm{b}}\pm 1$, for
$\mathrm{b}>1$, satisfies (
1)-(
4) and (
7), and
${\mathrm{p}}_{2}\ge 3$, it follows that a lower bound of
${\mathrm{p}}_{2}^{2}$ is 9, i.e.
${3}^{2}\le {\mathrm{p}}_{2}^{2}$. From Proposition 1, every value of this HPF within the interval
$[1,9)$ is, a priori, prime. Hence, the expressions
${2}^{2}+1$ and
${2}^{3}-1$ represent primes.
For $\mathrm{n}=1$, since 7 cannot be generated by an expression of the form ${2}^{\mathrm{b}}+1$, it follows that some primes may be represented by an HPF sum or a difference, not both. For $\mathrm{n}=2$, the number 7 can be represented by the HPF sum: ${2}^{2}+{3}^{1}$.
Violation of condition (
20), for
$k=1$, i.e. if
$\mathrm{HPF}\ge {3}^{2}$, neither guarantees nor precludes the primality of
$\mathrm{HPF}={2}^{\mathrm{b}}\pm 1.\mathrm{}$For example:
${2}^{4}+1$ and
${2}^{5}-1$ are both prime, but
${2}^{3}+1$ and
${2}^{4}-1$ are not.
3. Prime Generator Performance
In this section, the performance of the system (
1), (
2)-(
4) and (
7), viewed as a algebraic prime number generator, is evaluated theoretically and by using Monte Carlo simulation.
3.1. Definitions and Measures of Performance
From Proposition 1, the expression (
1), subject to (
2)-(
4), (
7), either generates a prime
$>{\mathrm{p}}_{\mathrm{n}}$, or a coprime to
${\mathrm{p}}_{1},{\mathrm{p}}_{2}\dots ,{\mathrm{p}}_{\mathrm{n}}$, with at most k terms in its prime factorization, where
$\mathrm{k}=\u230a\frac{\mathrm{log}\left(\mathrm{HPF}\right)}{\mathrm{log}\left({\mathrm{p}}_{\mathrm{n}+1}\right)}\u230b$.(25)
As discussed in the previous section, the special case, $\mathrm{k}=1$, implies that
$\mathrm{HPF}<{\mathrm{p}}_{\mathrm{n}+1}^{2}$(26)
and thus, the HPF, given by (
1), is a prime number in the semi-open interval [
${\mathrm{p}}_{\mathrm{n}+1},{\mathrm{p}}_{\mathrm{n}+1}^{2})$. To facilitate the analysis of the “prime generating” performance of (
1), its “prime generating power”,
$\mathrm{P}(\mathrm{n},\mathrm{k})$, is defined as a measure of how likely it is for (
1) to generate a prime.
Definition 1. The “prime generating power”,
$\mathrm{P}(\mathrm{n},\mathrm{k})$, of an HPF, given by (
1), subject to (
2)-(
4) and (
7), is defined by
$\mathrm{P}(\mathrm{n},\mathrm{k})=\frac{\mathrm{Number\; of\; HPF\; primes\; in}[{\mathrm{p}}_{\mathrm{n}+1}^{\mathrm{k}},\mathrm{}{\mathrm{p}}_{\mathrm{n}+1}^{\mathrm{k}+1})\mathrm{}}{\mathrm{Number\; of\; HPF\; outcomes\; in}[{\mathrm{p}}_{\mathrm{n}+1}^{\mathrm{k}},{\mathrm{p}}_{\mathrm{n}+1}^{\mathrm{k}+1})}$.(27)
From the above definition, it follows that
$\mathrm{P}(\mathrm{n},\mathrm{k})\le 1$. The quantity
$\mathrm{P}\left(\mathrm{n},\mathrm{k}\right)$ expresses the likelihood that (
1) generates a prime number within a given value range. Next, it is shown that
$\mathrm{P}(\mathrm{n},\mathrm{k})$ starts at 100% for
$\mathrm{k}=1$ and decreases as the value of
$\mathrm{k}$ increases.
Corollary 1. For any $\mathrm{n}\ge 1:P\left(\mathrm{n},1\right)=1,$ and $\mathrm{P}\left(\mathrm{n},\mathrm{k}\right)<1$ for $\mathrm{k}\ge 2$.
Proof. If
$\mathrm{k}=1$, from Proposition 1 and (
20), it follows that (
26) is true. Since the smallest non-prime having all its prime factors greater than
${\mathrm{p}}_{\mathrm{n}}$ is equal to
${\mathrm{p}}_{\mathrm{n}+1}^{2}$, the HPF expression, given by (1), will always generate a prime number in
$[{\mathrm{p}}_{\mathrm{n}+1},{\mathrm{p}}_{\mathrm{n}+1}^{2})$. Therefore, the numerator and denominator in (
27) are equal, and thus
$\mathrm{P}\left(\mathrm{n},1\right)=1$. For higher values of
$\mathrm{k}$, the HPF can take non-prime values, and therefore
$\mathrm{P}\left(\mathrm{n},\mathrm{k}\right)<1$.
Proposition 1 implies that, within the value range
$[{\mathrm{p}}_{\mathrm{n}+1},{\mathrm{p}}_{\mathrm{n}+1}^{2})$, expression (
1), subject to (
2)-(
4), (
7) generates a prime number with certainty, i.e.
$\mathrm{P}\left(\mathrm{n},1\right)=100\%$. In the general case, i.e. for HPF values
$\ge {\mathrm{p}}_{\mathrm{n}+1}^{2}$, this percentage is
$<1$, i.e. the value of
$\mathrm{P}\left(\mathrm{n},\mathrm{k}\right)$ decreases as
$\mathrm{k}$ increases, as described in Proposition 1. The variation of
$\mathrm{P}\left(\mathrm{n},\mathrm{k}\right)$ with respect to changes in the values of n and k is analyzed in the next section.
It is infeasible to exhaustively determine all possible HPF values in a given interval, since it cannot be precluded that, for some higher exponent values, the difference in
(1) would not generate a relatively small prime. Consider, for example, the following HPF, where
$\mathrm{n}=6$, given by
$\mathrm{HPF}={5}^{1}\bullet {13}^{3}-{2}^{4}\bullet {3}^{2}\bullet {7}^{1}\bullet {11}^{1}$
$\mathrm{HPF}=10985-11088=103$(28)
represents a prime, since
$\mathrm{HPF}<{\mathrm{p}}_{7}^{2}$, where
${\mathrm{p}}_{7}=17$. The two coprime terms in (
28) are, approximately, 100 times greater than the value of the HPF. Hence, it is possible to generate primes in
$[{\mathrm{p}}_{\mathrm{n}+1},{\mathrm{p}}_{\mathrm{n}+1}^{2})$ by subtracting coprime terms that are several orders of magnitude greater.
Under the assumption that (1) can generate every prime and coprime, it follows that evaluating its actual performance, given by $\mathrm{P}(\mathrm{n},\mathrm{k})$, is equivalent to assessing its predicted performance, $\widehat{\mathrm{P}}\left(\mathrm{n},\mathrm{k}\right)$, defined below.
Definition 2. The “predicted prime generating power”,
$\widehat{\mathrm{P}}\left(\mathrm{n},\mathrm{k}\right)$, of an HPF, given by (
1), subject to
(2)-(
4) and (
7), is defined by
$\widehat{\mathrm{P}}\left(\mathrm{n},\mathrm{k}\right)=\frac{\mathrm{A}(\mathrm{n},\mathrm{k})}{\mathrm{A}\left(\mathrm{n},\mathrm{k}\right)+\mathrm{B}(\mathrm{n},\mathrm{k})}$(29)
where $\mathrm{A}\left(\mathrm{n},\mathrm{k}\right)$ is the number of primes in $\left[{\mathrm{p}}_{\mathrm{n}+1}^{\mathrm{k}},\mathrm{}{\mathrm{p}}_{\mathrm{n}+1}^{\mathrm{k}+1}\right)$, and $\mathrm{B}\left(\mathrm{n},\mathrm{k}\right)$ is the number of composites in $\left[{\mathrm{p}}_{\mathrm{n}+1}^{\mathrm{k}},\mathrm{}{\mathrm{p}}_{\mathrm{n}+1}^{\mathrm{k}+1}\right)$, coprime to ${\mathrm{p}}_{1},{\mathrm{p}}_{2}\dots ,{\mathrm{p}}_{\mathrm{n}}$.
As previously mentioned, $\widehat{\mathrm{P}}\left(\mathrm{n},\mathrm{k}\right)$ is useful for two reasons:
(i) the computational complexity of computing all the solutions of (
1), subject to (
2)-(
4) and (
7), for
$\mathrm{n}\ge 10$ easily exceeds the computational capabilities of a typical computer system, since the two terms comprising the difference in the HPF expression, given by (
1), can reach extremely large values, even before generating an HPF prime within the desired range.
(ii) it is not known if every such prime and coprime can be represented by at least one solution in the form of (
1).
In the next section, the theoretically predicted $\widehat{\mathrm{P}}\left(\mathrm{n},\mathrm{k}\right)$ and the actual $\mathrm{P}(\mathrm{n},\mathrm{k})$, obtained by Monte Carlo simulation, are computed and compared.
3.2. Predicted vs. Simulated Performance
Since $\mathrm{B}\left(\mathrm{n},\mathrm{k}\right)=0$ for $\mathrm{k}=1$, it follows that $\widehat{\mathrm{P}}\left(\mathrm{n},1\right)=100\%$, for any HPF value in $\left[{\mathrm{p}}_{\mathrm{n}+1},\mathrm{}{\mathrm{p}}_{\mathrm{n}+1}^{2}\right)$. Therefore, a single value is assigned to $\widehat{\mathrm{P}}\left(\mathrm{n},\mathrm{k}\right)$ within each interval $\left[{\mathrm{p}}_{\mathrm{n}+1}^{\mathrm{k}},\mathrm{}{\mathrm{p}}_{\mathrm{n}+1}^{\mathrm{k}+1}\right)$, starting with $\widehat{\mathrm{P}}\left(\mathrm{n},1\right)=1$ for $\mathrm{k}=1$. For a range of $\mathrm{n},\mathrm{k}$ values, the number of primes and coprimes within each interval $\left[{\mathrm{p}}_{\mathrm{n}+1}^{\mathrm{k}},\mathrm{}{\mathrm{p}}_{\mathrm{n}+1}^{\mathrm{k}+1}\right)$ is computed, and the corresponding value of $\widehat{\mathrm{P}}\left(\mathrm{n},\mathrm{k}\right)$ for that interval is evaluated.
To avoid the time-consuming component of performing prime factorization for each HPF value, the computation of
$\mathrm{A}\left(\mathrm{n},\mathrm{k}\right)$,
$\mathrm{B}\left(\mathrm{n},\mathrm{k}\right)$ and
$\widehat{\mathrm{P}}\left(\mathrm{n},\mathrm{k}\right),\mathrm{}$utilizes the list of the first 1M primes from
. The results are summarized in the following table.
Table 1. Predicted performance, $\widehat{P}\left(n,k\right)$, for $n=3,4,5$ and $k=1,\dots ,5$.
k | n = 3 | n = 4 | n = 5 | Average |
1 | 100% | 100% | 100% | 100% |
2 | 63.6% | 67.9% | 67.5% | 66.4% |
3 | 50.3% | 52.6% | 49.2% | 50.7% |
4 | 39.7% | 41.2% | 39.0% | 40.0% |
5 | 33.0% | 34.1% | 32.1% | 33.1% |
From
Table 1, the values of
$\widehat{P}\left(n,k\right)$ do not vary significantly for
$n=3,4,5$. This observation has an interesting practical implication when searching for primes in higher order intervals, i.e.
$\left[{p}_{n+1}^{k},{p}_{n+1}^{k+1}\right)$ for
$k>1$: it implies that the likelihood that HPF is prime does not change significantly as
$n$ increases. The last column of
Table 1 shows the average values for each
$k$.
The above values of
$\widehat{P}\left(n,k\right)$ are compared to
$P\left(n,k\right)$, obtained by Monte Carlo simulation. To avoid runtime overflow errors, all exponent parameters in (
1) are capped. The Monte Carlo simulation results are summarized in
Table 2.
Table 2. Simulated performance, $P\left(n,k\right)$, for $n=3,4,5$, and $k=1,\dots ,5$.
k | n = 3 | n = 4 | n = 5 | Average |
1 | 100.0% | 100.0% | 100.0% | 100.0% |
2 | 66.7% | 65.7% | 65.6% | 66.0% |
3 | 52.4% | 47.3% | 50.9% | 50.2% |
4 | 38.3% | 42.7% | 37.6% | 39.5% |
5 | 29.4% | 33.1% | 32.9% | 31.8% |
From
Tables 1 and 2, it follows that:
(i) The average prime-generation performance of the HPF Prime and Coprime Generator (HPF PCG for short) is 50% or higher within the HPF range $\left[{\mathrm{p}}_{\mathrm{n}+1},{\mathrm{p}}_{\mathrm{n}+1}^{4}\right)$, i.e. for $k\le 3$.
(ii) When the HPF PCG generates a coprime number
q, the value of
$k$ from (
18) can be used to determine the maximum number of terms in the prime factorization of
q. This can be used to eliminate a significant number of prime factor combinations that do not generate a product with the same last digit as
q, making the prime factorization of HPF PCG coprimes more computationally efficient. This point is illustrated in Example 4.
Figure 1. Comparison of average predicted vs. simulated HPF prime-generation performance, for $k=1,\dots ,5$.
The results in
Tables 1 and 2 are shown graphically in
Figure 1. The average values of predicted performance,
$\widehat{P}\left(n,k\right)$, and simulated performance,
$P\left(n,k\right)$, are not significantly different for
$k=1,\dots ,5$.
Example 4. For $\mathrm{n}=4$, the HPF given by
$\mathrm{HPF}={2}^{1}\bullet {5}^{4}+{3}^{2}\bullet {7}^{1}=1250+63=1313$
$\mathrm{HPF}=13\bullet 101$(30)
generates a coprime number. Applying (
18), it follows that
$\mathrm{k}=2$. Therefore, the prime factorization of 1313 has at most 2 terms, i.e. a maximum prime factor cardinality of 2, and since HPF is coprime, it follows that HPF has exactly 2 prime factors.
Let p and q be primes, such that
$\mathrm{p}\bullet \mathrm{q}=1313$.(31)
Since p, q can only end in 1, 3, 7 or 9, for their product to end in 3, there can only be four last-digit combinations: (1,3), (3,1), (7,9), (9,7). Also, since $\mathrm{min}\left(\mathrm{p},\mathrm{q}\right)\ge 11$, it follows that $\mathrm{max}\left(\mathrm{p},\mathrm{q}\right)\le 119$. From Proposition 1, it follows that HPF is coprime to the first 4 primes. Thus, it is only necessary to test if HPF is divisible by an odd number w, where $\mathrm{w}\in [11,\mathrm{}119]$, and $\mathrm{w\; mod}10=1$ or $\mathrm{w\; mod}10=7$, i.e. a total of 44 possible numbers. This subset of possible factors may be further reduced, from 44 to 26, by excluding multiples of 3 or 7, e.g. 21, 27, 33, 39, 49 etc., generating an additional reduction of 41%. The remaining values are coprime with respect to the first 4 primes, and since $\mathrm{w}<{11}^{2}$, they are prime. The unique prime factorization solution is easily determined to be $\mathrm{p}=13$ and $\mathrm{q}=101$. This process significantly reduces the potential number of prime factors of an HPF-generated coprime, thus increasing computational efficiency. In general, the factorization of any HPF-generated coprime results in the determination of at least two primes greater than ${\mathrm{p}}_{\mathrm{n}}$.
As discussed in the previous example, the increased computational efficiency in searching for prime factors of HPF-generated coprimes is a result of the a priori knowledge of their maximum prime factor cardinality, established by Proposition 1 (part 3). In general, the computational savings in the prime factorization of an HPF coprime in [
${\mathrm{p}}_{\mathrm{n}+1}^{\mathrm{k}},{\mathrm{p}}_{\mathrm{n}+1}^{\mathrm{k}+1})$, generated by (
1), subject to (
2)-(
4) and (
7), are twofold:
(i) none of the n primes ${\mathrm{p}}_{1},{\mathrm{p}}_{2}\dots ,{\mathrm{p}}_{\mathrm{n}}$ should be considered, since they are not prime factors of any HPF coprime, and
(ii) since the prime factor cardinality of the HPF coprime is at most equal to k, where k is given by (
18), the subset of admissible prime factors, for each cardinality scenario, is reduced by considering only those candidate primes whose product ends in the same digit as the HPF coprime. Moreover, for each cardinality scenario, upper and lower bounds for the prime factors of the HPF can be derived, as discussed below.
Consider the case where the total prime factor cardinality of the HPF coprime equals m, where $\mathrm{m}\in [2,\mathrm{k}$]. It then follows that the upper and lower bounds for each prime factor ${\mathrm{q}}_{\mathrm{j}}>{\mathrm{p}}_{\mathrm{n}}$, of the HPF, are given by
$\mathrm{HPF}=\prod _{\mathrm{j}=1}^{\mathrm{m}}{\mathrm{q}}_{\mathrm{j}}$(32)
${\mathrm{p}}_{\mathrm{n}+1}\le \underset{\mathrm{j}}{\mathrm{min}}({\mathrm{q}}_{\mathrm{j}})\le \u230a\sqrt[\mathrm{m}]{\mathrm{HPF}}\u230b$(33)
$\underset{\mathrm{j}}{\mathrm{max}}({\mathrm{q}}_{\mathrm{j}})\le \u230a\frac{\mathrm{HPF}}{{\mathrm{p}}_{\mathrm{n}+1}^{\mathrm{m}-1}}\u230b$.(34)
Given that total prime factor cardinality includes any repeating prime factors, as explained in Section 2.1, (
32) does not imply that the
${\mathrm{q}}_{\mathrm{j}}$,
$\mathrm{j}=1,\dots ,\mathrm{m}$, are different. For example, if
$\mathrm{HPF}={13}^{4}$, then
$\mathrm{m}=4$ and
${\mathrm{q}}_{\mathrm{j}}=13$, for
$\mathrm{j}=1,\dots ,4.$Some of the computational efficiencies, described above, materialize even when the lower bound, ${\mathrm{p}}_{\mathrm{n}}+2$, is used, instead of ${\mathrm{p}}_{\mathrm{n}+1}$. Given that ${\mathrm{p}}_{\mathrm{n}}<{\mathrm{p}}_{\mathrm{n}}+2\mathrm{}\le {\mathrm{p}}_{\mathrm{n}+1}$, it follows that no HPF prime factor is less than ${\mathrm{p}}_{\mathrm{n}}+2$. Since there are at most k* prime factors, where ${\mathrm{k}}^{*}$ is given by
${\mathrm{k}}^{*}=\u230a\frac{\mathrm{log}\left(\mathrm{HPF}\right)}{\mathrm{log}\left({\mathrm{p}}_{\mathrm{n}}+2\right)}\u230b$(35)
the next step is to proceed by considering feasible factors for each cardinality value, up to ${\mathrm{k}}^{*}$. Any odds not coprime to ${\mathrm{p}}_{1},{\mathrm{p}}_{2}\dots ,{\mathrm{p}}_{\mathrm{n}}$, cannot be factors of the HPF coprime, since this would imply that the HPF is not coprime to ${\mathrm{p}}_{1},{\mathrm{p}}_{2}\dots ,{\mathrm{p}}_{\mathrm{n}}$. If the total prime factor cardinality of the HPF coprime is m, where $\mathrm{m}\in [2,{\mathrm{k}}^{*}$], the modified upper and lower bounds for each prime factor ${\mathrm{q}}_{\mathrm{j}}$, are given by:
${\mathrm{p}}_{\mathrm{n}}+2\le \underset{\mathrm{j}}{\mathrm{min}}({\mathrm{q}}_{\mathrm{j}})\le \u230a\sqrt[\mathrm{m}]{\mathrm{HPF}}\u230b$(36)
$\underset{\mathrm{j}}{\mathrm{max}}({\mathrm{q}}_{\mathrm{j}})\le \u230a\frac{\mathrm{HPF}}{{({\mathrm{p}}_{\mathrm{n}}+2)}^{\mathrm{m}-1}}\u230b$.(37)
As expected, the modified bounds, given by (
36)-(
37) are weaker than those in (
33)-(
34), respectively.
Example 5. Consider the factorization of the coprime HPF ($\mathrm{n}=4$), generated by
$\mathrm{HPF}={2}^{4}\bullet {3}^{3}\bullet {7}^{2}-{5}^{3}=2899=13\bullet 223$.(38)
Since no prime factor of 2899 is less than 7+2 = 9, it follows that
${\mathrm{k}}^{*}=\u230a\frac{\mathrm{log}\left(2899\right)}{\mathrm{log}\left(9\right)}\u230b=3.$(39)
and the total prime factor cardinality of 2899 is at most 3.
Consider the first case, where the prime factor cardinality, m, is $\mathrm{m}=2$, i.e. 2899 is assumed to be represented by
$2899={\mathrm{q}}_{1}\bullet {\mathrm{q}}_{2}$(40)
where
${\mathrm{q}}_{1},\mathrm{}{\mathrm{q}}_{2}$ are prime. It follows, from (
36)-(
37), that
$9\le \mathrm{min}({\mathrm{q}}_{1},\mathrm{}{\mathrm{q}}_{2})\le 53$(41)
$\mathrm{max}({\mathrm{q}}_{1},\mathrm{}{\mathrm{q}}_{2})\le 321.$(42)
From the subset of odd numbers satisfying (
41)-(
42), only those with compatible last digits need to be considered, i.e. whose product ends in 9. There are 4 possible combinations:
if ${\mathrm{q}}_{1}$ ends in 1 then ${\mathrm{q}}_{2}$ should end in 9
if ${\mathrm{q}}_{1}$ ends in 9 then ${\mathrm{q}}_{2}$ should end in 1
if ${\mathrm{q}}_{1}$ ends in 3 then ${\mathrm{q}}_{2}$ should end in 3
if ${\mathrm{q}}_{1}$ ends in 7 then ${\mathrm{q}}_{2}$ should end in 7.
Note that #1 and #2 are symmetric, and therefore only one of those should be considered, something that further increases the computational efficiency of the prime factor search. This search yields two factors of 2899, coprime to $2,\mathrm{}3,\mathrm{}5,\mathrm{}7$: 13 and 223.
It remains to be established that these factors are prime. Since $13<81$, it follows that 13 is smaller than the smallest HPF coprime, therefore 13 is prime. Since the smallest prime factor of 223 cannot exceed $\u230a\sqrt[2]{223}\u230b=14$, only 11 and 13 need to be considered. Since neither 11 nor 13 are factors, 223 is a prime factor. Given that prime factors are unique, the case m = 3 need not be considered.