Prove that at least one integer in any set of ten consecutive integers is relatively prime to the others in the set.

(In reply to Another proof--and extension. by Charlie)

Reducing the span to 8 as in my previous post makes it easier in one sense to get relative primes, in having fewer numbers that might share a factor, but harder in another in reducing the eligible candidates for being the relative prime.  So extension in the other direction could be of intereste.  The following program checks spans of 11 for numbers that are relatively prime and finds that the widest gap between numbers that are in fact prime relative to their preceding 10, is 10, so any span of 11 consecutive numbers contains at least one that is relatively prime to the rest:

max = 2 * 3 * 5 * 7 * 11
high = 11
span = 11
DIM hist(span, 5)
FOR n = 1 TO max + span
  FOR i = 1 TO span - 1
    FOR j = 1 TO 5
     hist(i, j) = hist(i + 1, j)
    NEXT
  NEXT i
  IF n MOD 2 = 0 THEN hist(span, 1) = 1:  ELSE hist(span, 1) = 0
  IF n MOD 3 = 0 THEN hist(span, 2) = 1:  ELSE hist(span, 2) = 0
  IF n MOD 5 = 0 THEN hist(span, 3) = 1:  ELSE hist(span, 3) = 0
  IF n MOD 7 = 0 THEN hist(span, 4) = 1:  ELSE hist(span, 4) = 0
  IF n MOD 11 = 0 THEN hist(span, 5) = 1:  ELSE hist(span, 5) = 0
  good = 1
  IF n < span THEN
   FOR i = 14 - n TO span - 1
    FOR j = 1 TO 5
     IF hist(i, j) = 1 AND hist(span, j) = 1 THEN good = 0
    NEXT
   NEXT
  ELSE
   FOR i = 1 TO span - 1
    FOR j = 1 TO 5
     IF hist(i, j) = 1 AND hist(span, j) = 1 THEN good = 0
    NEXT
   NEXT
  END IF
  IF good THEN
    PRINT n, n - prevN
    IF n > 1 AND n - prevN > maxdiff THEN maxdiff = n - prevN: maxAt = n
    prevN = n:
  END IF
NEXT n
PRINT maxdiff, maxAt

Posted by Charlie on 2004-03-03 09:50:20