Strangers On A Train

October 27, 2015

Let’s begin by making sure we understand the problem, because it’s tricky. Look at this table:

n  coprime to     a(n)
1                   2
2  2                3
3   3               4
4   3,4             5
5     4,5           7
6     4,5,7         9
7       5,7,9       8
8       5,7,9,8    11
9         7,9,8,11 13

We start with a(1) = 2, by definition; thus a(2) must be coprime to 2. Then a(2) = 3, which is the next smallest unused number and coprime to 2; thus a(3) and a(4) must be coprime to 3. Then a(3) = 4, which is the next smallest unused number and coprime to 3; thus a(3), a(4) and a(5) must all be coprime to 4. Then a(4) = 5, which is the next smallest unused number and coprime to 3 and 4; thus a(5), a(6), a(7) and a(8) must be coprime to 5. Then a(5) = 7; it can’t be 6 because it must be coprime to 4, so the next smallest unused number is 7, and a(6) through a(10) must be coprime to 7. And so on.

The problem is stated as looking forward (“the next n terms”) but is more easily programmed looking backward, and the table shows us how to do that: for any n, a(n) must be coprime to the most recent ⌊n/2⌋ values in the sequence. For instance, when n is 9, a(9) must be coprime to the last ⌊9/2⌋ = 4 values in the sequence, a(8), a(7), a(6) and a(5), which are 11, 8, 9 and 7.

We track the “smallest number not yet used” in an ordered available list that is initially [3,4] and is extended each time a new sequence member is generated with the numbers up to the next larger prime number.

Thus, we calculate the first n elements of the sequence like this:

(define (strangers n)
  (let loop1 ((k 1) (strange (list 2)) (avail (list 3 4)))
    (if (<= n k) (reverse strange)
      (let loop2 ((cs avail)) ; list of candidates
        (if (null? cs) (error 'strangers "null candidate list")
          (let ((c (car cs)))
            (if (all? (lambda (x) (coprime? x c))
                      (take (quotient (+ k 1) 2) strange))
                (loop1 (+ k 1) (cons c strange)
                       (append (remove c avail)
                               (range (+ (last cs) 1)
                                      (+ (next-prime (last cs)) 1))))
                (loop2 (cdr cs)))))))))

And here are the first 61 terms of the sequence, which match the list at A247665:

> (strangers 61)
(2 3 4 5 7 9 8 11 13 17 19 23 15 29 14 31 37 41 43 47 53 59
 61 67 71 73 25 27 79 83 16 49 89 97 101 103 107 109 113 121
 127 131 137 139 149 151 157 163 167 169 173 179 181 191 85
 193 57 197 199 211 223)

You can run the program at http://ideone.com/0miAAH, where you will also see all of the remaining pieces of code.

Advertisements

Pages: 1 2

3 Responses to “Strangers On A Train”

  1. Paul said

    In Python.

    from fractions import gcd
    def strangers(s):
        seq = [s]
        available = list(range(s+1, next_prime(s)+1))
        yield s
        while True:
            last = available[-1]
            available.extend(range(last+1, next_prime(last)+1))
            for e in available:
                if all(gcd(e, sj) == 1 for sj in seq[-len(seq)//2:]):
                    seq.append(e)
                    available.remove(e)
                    yield(e)
                    break
    g = strangers(2)
    print([next(g) for _ in range(61)])
    
  2. wert310 said

    Haskell

    strangers s = loop s [2] [3..]
        where
          getAvail (x:xs) seq
                   | and $ map (\z->(gcd z x)==1)
                               (take (((length seq)+1)`div`2) seq) = x
                   | otherwise = getAvail xs seq
          loop 1 seq _ = reverse seq
          loop s seq available =
              let av = getAvail available seq
              in loop (s-1) (av:seq) (filter (/=av) available)
    
  3. matthew said

    Here’s some C++11:

    #include <list>
    #include <vector>
    #include <iostream>
    
    // gcc can optimize tail recursions now.
    int gcd(int a, int b) { return (b == 0) ? a : gcd(b,a%b); }
    
    int main(int argc, char *argv[]) {
      auto count = atoi(argv[1]);
      std::vector<int> seq;
      std::list<int> avail;
      auto nextavail = 2;
      for (auto n = 0; n < count; n++) {
        for (auto it = avail.begin(); ; it++) {
          // Extend available list if necessary
          if (it == avail.end()) {
            it = avail.insert(it, nextavail++);
          }
          // Check coprimality
          for (auto i = n/2; i < n; i++) {
            if (gcd(seq[i], *it) != 1) goto failed;
          }
          // Found, so add to sequence & remove from available
          seq.push_back(*it);
          avail.erase(it);
          break;
        failed:
          continue;
        }
      }
      for (auto n: seq) std::cout << n << " ";
      std::cout << "\n";
    }
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: