Divisors of consecutive sequences

Question

How can I prove that any sequence of $\leq16$ consecutive integers contains at least one number which has no divisor in common with any of the other numbers?

I know that it's true for a sequence of two consecutive integers, as $\gcd(x,x+1)=1$, but I can't prove it for any other lengths of sequence, let alone up to $16$.

Answer 1

Suppose the contrary. Let us consider such a counterexample sequence, $$ n+1,\ n+2,\ n+3,\ \dots\ ,\ n+14,\ n+15,\ n+16, $$ for an $n\ge 0$, $n\in \Bbb Z$, with the property that

• for each $j$ in $1,2,\dots, 16$,

  • there exists a $k$ in $1,2,\dots, 16$, $k\ne j$,

    • so that $n+j$ and $n+k$ share a common prime factor, $p=p(j,k)$, to have no problems which choices, we take the minimal prime factor always.

Then for all pairs of different indices $j,k$ from $1$ to $16$, the prime $p(j,k)$ divides the difference $(n+j)-(n+k)=(j,k)$, so this prime number is one among the primes between $2$ and $16-1$. So $p(j,k)\in\{2,3,5,7,11,13\}$.

The lowest common multiple of these numbers is their product,

sage: prod( primes(15) )
30030
sage: _.factor()
2 * 3 * 5 * 7 * 11 * 13

After subtracting a multiple of $30030$ from $n$, the same divisibility structure is kept, so we can assume $0\le n< 30030$. This is a case for the computer in this century. (A problem with a quick finite check of cases, that has no structural importance, should be always solved in this way in my opinion, if the effort is minimal to do it. And here it is minimal.) I will use sage, the code is self-explanatory.

N = 16
R = [1..N]
bad_n_values = []
matches = {}    # dictionary n -> j such that n+j shares no prime factors

for n in [0..prod(primes(N))-1]:

    matches[n] = None    # so far
    for j in R:
        k_match_was_found = False    # so far
        for k in R:
            if k == j:    continue
            if gcd(n+j, n+k) > 1:
                k_match_was_found = True
                break    # the k loop
        if not k_match_was_found:
            matches[n] = j
            break    # the j loop
    # if this point is reached, then matches[n] remains None

if None in matches.values():
    print "NO MATCHES for the following values of n:"
    print [ j for j in matches.keys() if matches[j] == None ]

else:
    print "OK"

The code gives its

OK

$\blacksquare$

---

Examples:

(The code does a bad job for $n=0$, well, $11$ and/or $13$ share no common divisors will all the rest.)

After this, let us see the values found for some specific $n$, for instance:

sage: for n in [1..20]: print n, '->', n+matches[n]
1 -> 11
2 -> 11
3 -> 11
4 -> 11
5 -> 11
6 -> 13
7 -> 13
8 -> 13
9 -> 13
10 -> 17
11 -> 17
12 -> 17
13 -> 17
14 -> 17
15 -> 17
16 -> 17
17 -> 19
18 -> 19
19 -> 23
20 -> 23

So the computer picks at the beginning the "first relevant prime". This can be converted to an idea.

---

An alternative (computational) proof would be to see which is the "maximal gap length" in the list of numbers from $17$ (the first cases are clear) up to $30030$ which are relatively prime to $30030$. It is $22$, so we have to examine the situation closer. Which are the intervals with a gap $>16$? Here they are:

P = prod(list(primes(15)))    # 30030
L = [ n for n in [17..30030.next_prime()] if gcd(n, P) == 1 ]

gaps_list = [ L[k+1] - L[k] for k in range(len(L)-1) ]
maximal_gap = max( gaps_list )
print "Maximal gap is", maximal_gap
print "Following intervals have a gap >16:"
for k in range(len(L)-1):
    if L[k+1] - L[k] > 16:
        print L[k], L[k+1], ':: gap =',  L[k+1] - L[k]

Results:

Maximal gap is 22
Following intervals have a gap >16:
2183 2201 :: gap = 18
5749 5767 :: gap = 18
9109 9127 :: gap = 18
9439 9461 :: gap = 22
13339 13357 :: gap = 18
16673 16691 :: gap = 18
20569 20591 :: gap = 22
20903 20921 :: gap = 18
24263 24281 :: gap = 18
27829 27847 :: gap = 18

Only for values of $n$ between the listed "intervals" we have to do something. In each case, some "special primes", $11$ and/or $13$ will help us. For instance:

Sage code:

for k in range(len(L)-1):
    if L[k+1] - L[k] > 16:
        print "INTERVAL (", L[k], ',', L[k+1], ' ) :: gap =',  L[k+1] - L[k]
        for n in range( L[k]+1, L[k+1]-16 ):
            solution = n + matches[n]
            print "\tn = %s -> %s = %s" % ( n, solution, solution.factor() )

Results:

INTERVAL ( 2183 , 2201  ) :: gap = 18
        n = 2184 -> 2197 = 13^3
INTERVAL ( 5749 , 5767  ) :: gap = 18
        n = 5750 -> 5759 = 13 * 443
INTERVAL ( 9109 , 9127  ) :: gap = 18
        n = 9110 -> 9119 = 11 * 829
INTERVAL ( 9439 , 9461  ) :: gap = 22
        n = 9440 -> 9449 = 11 * 859
        n = 9441 -> 9449 = 11 * 859
        n = 9442 -> 9449 = 11 * 859
        n = 9443 -> 9449 = 11 * 859
        n = 9444 -> 9451 = 13 * 727
INTERVAL ( 13339 , 13357  ) :: gap = 18
        n = 13340 -> 13351 = 13^2 * 79
INTERVAL ( 16673 , 16691  ) :: gap = 18
        n = 16674 -> 16679 = 13 * 1283
INTERVAL ( 20569 , 20591  ) :: gap = 22
        n = 20570 -> 20579 = 13 * 1583
        n = 20571 -> 20579 = 13 * 1583
        n = 20572 -> 20579 = 13 * 1583
        n = 20573 -> 20579 = 13 * 1583
        n = 20574 -> 20579 = 13 * 1583
INTERVAL ( 20903 , 20921  ) :: gap = 18
        n = 20904 -> 20911 = 11 * 1901
INTERVAL ( 24263 , 24281  ) :: gap = 18
        n = 24264 -> 24271 = 13 * 1867
INTERVAL ( 27829 , 27847  ) :: gap = 18
        n = 27830 -> 27841 = 11 * 2531

This would be a second solution.

$\blacksquare$

I inserted this code, its print, and the special solutions in the above "hard cases" to see the difficulty of a "human solution". It is really a "coincidence" that even in the above cases of intervals with a bigger gap the first divisor of $13$ lives "in the middle", and it is just one in the interval.