## 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

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