All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Not So Neighborly (Posted on 2004-03-03)
Prove that at least one integer in any set of ten consecutive integers is relatively prime to the others in the set.

 See The Solution Submitted by Aaron Rating: 4.0000 (4 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 Extension in the other direction | Comment 6 of 7 |
(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

 Search: Search body:
Forums (0)