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.
In Python.
Haskell
Here’s some C++11: