Recamn's sequence

def recaman(n):

Compute and return the first n terms of the Recamn's sequence, starting from the term a1 = 1. See the linked definition for this sequence as it is defined on Wolfram Mathworld.

Note how the definition for the current next element depends on whether a particular number is already part of the previously generated part of the sequence. To let your function execute in a speedy fashion even when generating a sequence that contains millions of elements, you should use a set to keep track of which values are already part of the previously generated sequence. This way you can generate each element in constant time, instead of having to iterate through the entire previously generated list like some "Shlemiel" would have done. The better technique that saves time by using more memory can create this list arbitrarily far in linear time, and should therefore be fast even for millions of elements, at least until it runs out of memory.

n Expected result

10 [1, 3, 6, 2, 7, 13, 20, 12, 21, 11]

1000000 (a list of million elements whose last five elements are [2057162, 1057165, 2057163, 1057164, 2057164] )