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.

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