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.
Programming Praxis 
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)])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)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"; }