Is every prime is the largest prime factor in some prime gap

analytic-number-theorydivisibilityelementary-number-theorynumber theoryprime numbers

Definition: In the gap between any two consecutive odd primes we have one or more composite numbers. We define the largest of among all the prime factor of these composite as the maximal prime factor of the gap.

Claim: Every prime is a maximal prime factor for some prime gap.

I am looking for a proof or disproof.

Update 21 Dec 2019: Conjecture verified for $p \le 10^{10}.$

Update 7 Dec 2019: Question has been posted in MO

Update 14-Aug-2020: Fixed source code

p_test = 2                                    # contains the prime being tested
high = 0                                      # current deepest search
target = step = 10^6                          # target and step for tracking progress

while True:
    m = 2                                     # current multiplier
    p = previous_prime(next_prime(m*p_test))  # start of prime gap

    while True:
        q = next_prime(p)                     # end of prime gap
        n = p + 1
        mf= 2                                 # starting maximal factor

        while n < q:
            mf_n = prime_divisors(n)[-1]      # contains current maximal factor
            if mf_n > mf:
                mf = mf_n                     # contains final maximal factor
            if mf < p_test:
                n = n + 1
            else:
                break                         # early exit if bigger maximal factor found

        if mf == p_test:
            break                             # exit loop when maximal factor is found
        m = m + 1
        p = previous_prime(next_prime(m*p_test))

    if m > high:                              # Display new deepest search
        print (p, m)
        high = m

    if p > target:                            # Display progress
        print ("Reached", target)
        target = target + step

    p_test = next_prime(p_test)

Best Answer

As requested by Nilotpal Kanti Sinha in the comments, here's the code I used to check maximal prime factor occurrences for all primes up to $4\cdot10^8$.

This is written in Sage, which is basically Python 2 with built-in maths. Hopefully the functions next_prime(), previous_prime(), prime_divisors() and max() are all self-explanatory.

The approach is to test successive multiples of each prime to see if they are the maximal prime factor in the relevant prime gap.

def get_max_prime(n):
# Find the maximal prime factor in the prime gap containing n
    pp = previous_prime(n)
    np = next_prime(n)
    fs = set([])   # Set of all prime factors in the gap

    for c in range(pp+1, np):
        for p in prime_divisors(c):
            fs.add(p)
    return max(fs)

# target and step for tracking progress
target = 10**6
step = 10**6

p = 3       # The prime to be tested
high = 0    # Tracks the deepest search

while True:
    q = p   # q will be a multiple of p
    m = 0   # Will contain the maximal prime factor in a gap
    c = 1   # Multiplier

    while(m != p):
        c = c + 1
        q = p * c
        m = get_max_prime(q)

    if c > high:     # Display new deepest search
        print p,c
        high = c

    if p > target:   # Display progress
        print "Reached", target
        target = target + step

    p = next_prime(p)
Related Question