Is there any way to find a row of numbers with many prime factors?

80 Views Asked by At

According to the Erdos–Kac theorem, $\sigma=\frac{\omega(n)-\log\log n}{\sqrt{\log\log n}}$ is close to the standard normal distribution, where $\omega(n)$ is the number of distinct prime factors on $n$. We can expect that the $\sigma$ rarely exceed, for example, 5, but it is not that difficult to find such numbers. For example,

  • $p_n\#$ has $n$ distinct prime factors, i.e., $\omega(p_n\#)=n$, and $\sigma=5.07$ for $n=13$.
  • $2^{1000}-1$ can be divided by $2^2-1, 2^4-1, 2^5-1,2^8-1,\ldots,2^{500}-1$, and $\omega(2^{1000}-1)=34$, $\sigma=10.74$.
  • A Fibonacci number $F_{1000}$ can be divided by $F_2, F_4, F_5, F_8, F_{10}, \ldots, F_{500}$, and $\omega=23, \sigma=6.77$.

However, their neighbors does not. For example, $2^n-2=2(2^{n-1}-1)$ have algebraic factors, but $2^n-3$ does not and $2^n$ has only the factor $2$. $F_{2m+1}\pm1, F_{2m+1}\pm2$ can be factorized as follows, but $F_{2m+1}\pm3$ does not seem to have algebraic factors.

  • $F_{4n+1}-2=F_{2n-1}\cdot L_{2n+2}$, $F_{4n+3}-2=F_{2n+3}\cdot L_{2n}$
  • $F_{4n+1}-1=F_{2n}\cdot L_{2n+1}$, $F_{4n+3}-1=F_{2n+2}\cdot L_{2n+1}$
  • $F_{4n+1}+1=F_{2n+1}\cdot L_{2n}$, $F_{4n+3}+1=F_{2n+1}\cdot L_{2n+2}$
  • $F_{4n+1}+2=F_{2n+2}\cdot L_{2n-1}$, $F_{4n+3}+2=F_{2n}\cdot L_{2n+3}$

So, is there an easy way or formula to find a succession of numbers such that each has many prime factors, especially more than five in a row?

1

There are 1 best solutions below

0
On BEST ANSWER

One method to determine an arbitrarily long list of consecutive integers, with each one having at least any specified minimum number of distinct prime factors, is by using the Chinese remainder theorem to solve a set of modular equations with appropriate coprime moduli.

For example, to find some positive integer $k$ (e.g., $k \ge 5$) consecutive integers starting at $n$ with each integer having at least $6$ distinct prime factors, a basic set of equations which could be used is (note $p_i$ is the $i$'th prime)

$$\begin{equation}\begin{aligned} n \equiv 0 & \pmod{2(3)(5)(7)(11)(13)} \\ n \equiv -1 & \pmod{17(19)(23)(29)(31)(37)} \\ & \qquad \qquad \qquad \vdots \\ n \equiv -(k - 1) & \pmod{p_{6k-5}(p_{6k-4})(p_{6k-3})(p_{6k-2})(p_{6k-1})(p_{6k})} \end{aligned}\end{equation}$$

Note, though, there's also a basic optimization which can be used. Since the first equation means $n$ is even, then $n + 2$, $n + 4$, etc., are also all even. Thus, one prime factor of the modulus in each of the $3$'rd, $5$'th, etc., equations can be removed. Considering $3$ also divides $n$ (and thus $n + 3$, $n + 6$, etc.), then the $4$'th, $7$'th, etc., equations can each have a prime factor removed from their moduli. This process can be repeated for additional small prime factors.