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.

Posted by programmingpraxis

Filed in Exercises

3 Comments »

3 Responses to “Strangers On A Train”

Paul said

October 27, 2015 at 9:40 AM

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)])

wert310 said

October 27, 2015 at 11:20 PM

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)

matthew said

October 28, 2015 at 8:59 PM

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";
}

Programming Praxis