Newman-Conway sequence

The recursive sequence defined by the recurrence relation a(n) = a(a(n - 1)) + a(n - a(n - 1)) with a(1) = a(2) = 1. The first few values are 1, 1, 2, 2, 3, 4, 4, 4, 5, 6, ... (OEIS A004001; Wolfram 2002, pp. 129-130, sequence (c)). Conway showed that lim_(n->∞) a(n)/n = 1/2 and offered a prize of $10000 to the discoverer of a value of n for which left bracketing bar a(i)/i - 1/2 right bracketing bar <1/20 for i>n. The prize was subsequently claimed by Mallows, after adjustment to Conway's "intended" prize of $1000, who found n = 1489.

blancmange function | Hofstadter's Q-sequence | Mallows' sequence

Douglas Hofstadter | John Conway