Помогите, пожалуйста, с задачкой.

Взята она с сайта с олимпиадными задачами https://www.spoj.pl/problems/MRECAMAN/
Суть её следующая.
Последовательность Recaman-а определена так:

a0 = 0
Для m, больших 0:
a(m) = a(m-1) - m, если эта разность больше нуля и её до этого момента в последовательности не было;
a(m) = a(m-1) + m, иначе.

Вот первые несколько членов последовательности:
0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9...

Задание состоит в том, чтобы по введённому порядковому номеру k вывести k-ый член последовательности.

Вообще, эту задачу мне нужно сдать на Хашкеле, но пока что я хочу сдать её на другом языке, который я знаю чуть получше (ruby, C). И возникла проблема с придумыванием алгоритма, поскольку решение в лоб (в смысле, просто переписать рекуррентное соотношение, ну и добавить поиск по массиву для проверки, встречалось ли число в последовательности ) не годится для больших k (0 <= k <= 500000). Буду очень признателен, если подскажете эффективное решение данной задачи.