Strangers On A Train

October 27, 2015

In Sloane’s Encyclopedia, sequence A247665 is defined as

a(1) = 2; thereafter a(n) is the smallest number not yet used which is compatible with the condition that a(n) is relatively prime to the next n terms. The sequence begins 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, …

The sequence was submitted by Amarnath Murthy and given to Neil Sloane as a birthday present. Sloane calls the sequence “Strangers on a Train” after the psychological thriller novel by Patricia Highsmith and subsequent film by Alfred Hitchcock, because the nth element of the sequence has no factors in common with the next n elements (they are “strangers”).

Your task is to write a program that generates the sequence. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: