6
$\begingroup$

Is there a published result that says the following?

Let $p$ be an prime number. Then for all integer $n>p$ there is at least one number in the consecutive sequence $2n,2n+1,2n+2,\ldots,2n+2p-1$ that is relatively prime to all prime numbers less than or equal to $p$.

For example, if $p=5$ and $n=17$, the sequence $34,35,36,37,38,39,40,41,42,43$ has several numbers not divisible by $2,3,5$. Now this just needs to be true for any $n>p$ and any prime $p$.

I have already asked my colleague who received his Ph.D. in Number Theory. He suggested I pose it to a wider audience, hence why I'm here. Any suggestions on results would be greatly appreciated.

$\endgroup$
  • $\begingroup$ I'd say we know something a bit stronger which is, the sequence of prime numbers contains arithmetic subsequences of arbitrary length which is due to Green and Tao (2004). $\endgroup$ – Raito Nov 12 '17 at 23:26
  • 3
    $\begingroup$ @Raito you are misunderstanding the question due to the ambiguous use of the word "any": sometimes it means some ("does this equation have any solution?") and sometimes it means all (for any $\varepsilon > 0\ldots$). When writing "for any integer $n > p$" I believe the intention is "for all integers $n > p$," in which case the Green--Tao theorem doesn't help. $\endgroup$ – KCd Nov 13 '17 at 2:20
  • $\begingroup$ @KCd is right. I apologize for ambiguous use of "any". I have edited it to make it more clear. $\endgroup$ – John Asplund Nov 13 '17 at 12:18
4
$\begingroup$

The conjecture is false.

Let $p_1, p_2, p_3, \dots$ be the primes. Define the primorial Jacobsthal function $h(k)$ to be the smallest length $\ell$ such that every consecutive sequence of integers of length $\ell$ contains a number relatively prime to $p_1, \dots p_k$. Your conjecture is equivalent to the assertion that $h(k) \le 2 p_k$.

(The condition is invariant upon adding or subtracting multiples of $P = \prod_{i=1}^k p_i$, so the condition that $n > p$ is irrelevant, and for fixed $p$ the conjecture can be verified by a finite calculation; it suffices to examine consecutive sequences of integers between $0$ and $P - 1$ inclusive.)

According to the table of values of $h(k)$ in the linked paper we have

$$p_{14} = 43, h(14) = 90 > 86$$

so there is a consecutive sequence of $89$ integers none of which is relatively prime to the primes up to $43$. This is the smallest counterexample.

You can show that $h(k) \ge 2p_{k-1}$ by constructing a consecutive sequence of integers of length $2p_{k-1} - 1$ none of which is relatively prime to $p_1, \dots p_k$. This can be done by considering the integers $n - a, n - a + 1, \dots n + a - 1, n + a$ where $n$ is a solution to the system of congruences

$$n \equiv 0 \bmod p_1 \dots p_{k-2}$$ $$n-1 \equiv 0 \bmod p_{k-1}$$ $$n+1 \equiv 0 \bmod p_k$$

and $a = p_{k-1} - 1$. This construction is actually best possible for $p_k \le 19$; for example when $p_k = 19$ it produces the sequence $60044, \dots 60076$. It first stops being best possible when $p_k = 23$, where this construction gives a sequence of length $37$ but the longest sequence has length $39$ (namely $20332472, \dots 20332510$).

For completeness' sake here is the (very sloppy, I'm sure) Python script I used to test the conjecture; it allowed me to compute enough values of $h(k)$ that I could look it up on the OEIS, and looking at the longest sequences led me to the construction above. Note that it computes $h(k) - 1$, the length of the longest sequence of integers not relatively prime to $p_1, \dots p_k$.

from sympy import sieve
from math import gcd
from operator import mul
import functools as ft

def longest(p):
    primes = list(sieve.primerange(1, p+1))
    product = ft.reduce(mul, primes, 1)

    biglist = list(range(0, primordial(p)))

    def isrelprime(n):
        answer = True
        for p in primes:
            if gcd(n,p) != 1:
                answer = False
        return answer

    best = 0
    bestlen = 0
    curlen = 0
    for i in biglist:
        if not isrelprime(i):
            curlen += 1
        else:
            curlen = 0
        if curlen > bestlen:
            best = i
            bestlen = curlen

    print("\nPrime : " + str(p))
    print("Best : " + str(best))
    print("Length : " + str(bestlen))

    for i in range(0, bestlen):
        print(str(best - i) + " has gcd " + str(gcd(best - i, product)))

primes = list(sieve.primerange(1, 20))
for p in primes:
    longest(p)

And here's a little bit of extra code for computing the gcd of a particular sequence of consecutive integers with the product of the primes up to some prime.

def check(n, p, len):
    primes = list(sieve.primerange(1, p+1))
    product = ft.reduce(mul, primes, 1)
    for i in range(0, len):
        print(str(n - i) + " has gcd " + str(gcd(n - i, product)))

check(60076, 19, 33)
check(20332510, 23, 39)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.