15
$\begingroup$

Definition: Highly composite prime gap

The three composite numbers between the consecutive primes $643$ and $647$ each have at least three distinct prime factors. This is the first occurrence of prime gap of length $> 1$ where each composite number in the gap has at least $k = 3$ distinct prime factors. We call prime gap between $643$ and $647$ as the highly composite prime gap of order $3$. We have the highly composite prime gaps for $k = 3,4,5$ and $6$ as follows:

  • $k = 3; p = 643$
  • $k = 4; p = 51427$
  • $k = 5; p = 8083633$
  • $k = 6; p = 1077940147$
  • $k = 7; p = 75582271489$

Question 1: Are there infinitely many highly composite prime gaps of order $k \ge 3$?

Question 2: Given $k$ is there always a highly composite gap of order $k$?

An ordinary linear regression between $k$ and $\log p$ gives a surprisingly strong fit with $R^2 \approx 0.99915$. Although it is based on only six data points, this suggests a relationship of the form $p \sim ab^k$ forsome fixed $a$ and $b$.

Definition: Maximal highly composite gap

The maximal highly composite gap is defined as a prime gap which is longer than any previous gap and each composite in the gap has at least $3$ distinct prime factors.

Update: The longest such gap I have found is of $75$ consecutive composite between the primes $535473480007$ and $535473480083$.

Question 3: Are there arbitrarily long prime gaps in which each composite number in the gap has at least three distinct prime factors?

Update: Posted in MO since it is unanswered in MSE.

$\endgroup$
4
  • $\begingroup$ I think you meant prime gap of length $\geq 3$ in the second sentence. Otherwise, the composite number between $29$ and $31$ has three distinct prime factors. $\endgroup$
    – arbashn
    Jun 25, 2021 at 6:50
  • $\begingroup$ @arbashn Yes right. corrected $\endgroup$
    – Nilotpal Sinha
    Jun 25, 2021 at 6:53
  • 2
    $\begingroup$ Note that for any two successive prime numbers, $p_a$ and $p_b$, the interval $(p_a^2,p_b^2)$ contains at least one semiprime, $p_ap_b$, which does not have at least three distinct prime factors. So arbitrarily long gaps (of the kind in the question) require arbitrarily large gaps between successive primes. Finding examples of such gaps will require working with very large numbers. $\endgroup$
    – Keith Backman
    Jun 26, 2021 at 16:11
  • 1
    $\begingroup$ "Initial term of first run of exactly $n$ consecutive numbers with $3$ distinct prime factors" is tabulated at oeis.org/A185032 (but it's not quite what you want, still, the references may point to something). $\endgroup$
    – Gerry Myerson
    Jun 28, 2021 at 4:43

1 Answer 1

Reset to default
17
$\begingroup$

Yes, there are arbitrarily long sequences of integers each of which has at least $3$ prime factors, and the same is true for any $k$ in lieu of $3$.

Given arbitrary positive integers $k$ and $m$, choose integers $n_1,n_2,\ldots,n_m$ with the following properties:

  1. Each $n_i$ has at least $k$ distinct prime factors;
  2. The $n_i$ are pairwise relatively prime.

It is obvious that such a sequence of integers exists (just pick a batch of distinct primes for each $i$, and multiply them).

Now, using the Chinese Remainder Theorem we can find an integer $N$ such that for each $i$, $N \equiv -i \pmod{n_i}$, or in other words $N+i \equiv 0 \pmod{n_i}$. Therefore, the numbers $N+1, N+2, \ldots, N+m$ all have at least $k$ distinct prime factors.

EDIT: the question seems to further demand that the long stretch of “very composite” integers be bookended by actual primes. This proof does not guarantee that, and in fact I suspect this is very hard to guarantee.

$\endgroup$
5
  • 2
    $\begingroup$ The exact question required the gap to be between two primes. Is there a way to adjust your proof to this? (this does prove the opposite to what I tried to show in my answer though, which is why I deleted mine, thanks) $\endgroup$
    – Lassadar
    Jun 25, 2021 at 6:50
  • 3
    $\begingroup$ Yes, it’s not super clear but I see what you mean. No, I think it would be quite hard to adjust my proof to handle this. At the ends of a stretch of integers with at least 3 prime factors we will find integers with fewer than 3, but they may well have 2 and I don’t see a way to avoid that. $\endgroup$
    – Alon Amit
    Jun 25, 2021 at 6:52
  • 3
    $\begingroup$ By Dirichlet’s theorem on prime progressions there could be a way to ensure that $N$ or $N+m+1$ is prime. But to force both of them to be primes, you basically need to make a prime gap and that is really much harder than CRT. $\endgroup$
    – Aphelli
    Jun 25, 2021 at 7:46
  • 1
    $\begingroup$ At least we can say that $N$ and $N+m+1$ can't both be prime if $m$ is even... $\endgroup$
    – Troposphere
    Jun 25, 2021 at 7:59
  • 4
    $\begingroup$ Probably you could get as close as “one end is prime, the other end is either prime or semiprime”, using sieve methods. Beyond that does sound intractable by this approach. $\endgroup$
    – Erick Wong
    Jun 25, 2021 at 8:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .