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

Home > Numbers
Not So Neighborly (Posted on 2004-03-03) Difficulty: 4 of 5
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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (2)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information