Hofstadter sequences are a family of related integer sequences, among which the first ones were described by an American professor Douglas Hofstadter in his book Gödel, Escher, Bach. 

### Task
Today we will be implementing the rather chaotic recursive sequence of integers called Hofstadter Q.
The Hofstadter Q is defined as:

As the author states in the aforementioned book:It is reminiscent of the Fibonacci definition in that each new value is a sum of two
previous values-but not of the immediately previous two values. Instead, the two
immediately previous values tell how far to count back to obtain the numbers to be added
to make the new value.
The function produces the starting sequence:  
`1, 1, 2, 3, 3, 4, 5, 5, 6 . . .`  
Test info: 100 random tests, n is always positive
Good luck!

Source: codewars | Difficulty: EASY
Tags: Complete search

Starter code: def hofstadter_Q(n):
	

Solutions:
def hofstadter_Q(n):
	try:
		return hofstadter_Q.seq[n]
	except IndexError:
		ans = hofstadter_Q(n - hofstadter_Q(n - 1)) + hofstadter_Q(n - hofstadter_Q(n - 2))
		hofstadter_Q.seq.append(ans)
		return ans
hofstadter_Q.seq = [None, 1, 1]


def hofstadter_Q(n):
	q = [1, 1]
	while len(q) < n:
		q.append(q[-q[-1]] + q[-q[-2]])
	return q[-1]


def hofstadter_Q(n):
	lst = [0, 1, 1]
	while len(lst) <= n:
		lst += [lst[-lst[-1]] + lst[-lst[-2]]]
	return lst[n]


def hofstadter_Q(n):
	a = [None, 1, 1]
	for i in range(3, n + 1):
		a.append(a[i - a[-1]] + a[i - a[-2]])
	return a.pop()


li = [1, 1]
while len(li) != 1000:
	li.append(li[-li[-1]] + li[-li[-2]])
hofstadter_Q = lambda n: li[n - 1]


import sys
sys.setrecursionlimit(10000)
from functools import lru_cache

@lru_cache(maxsize=None)
def Q(n):
	if n <= 2:
		return 1
	return Q(n - Q(n - 1)) + Q(n - Q(n - 2))

def hofstadter_Q(n):
	return Q(n)


memory = {1: 1, 2: 1}

def hofstadter_Q(n):
	if n not in memory.keys():
		memory[n] = hofstadter_Q(n - hofstadter_Q(n - 1)) + hofstadter_Q(n - hofstadter_Q(n - 2))
	return memory[n]


hofstadter_Q_values = [0, 1, 1]

def hofstadter_Q(n):
	values = hofstadter_Q_values
	for i in range(len(values), n + 1):
		values.append(values[i - values[i - 1]] + values[i - values[i - 2]])
	return values[n]


def hofstadter_Q(n):
	a = [1, 1]
	for i in range(2, n):
		a.append(a[i - a[i - 1]] + a[i - a[i - 2]])
	return a[n - 1]


from functools import lru_cache

@lru_cache(maxsize=1024)
def hofstadter_Q(n):
	if n in (1, 2):
		return 1
	return hofstadter_Q(n - hofstadter_Q(n - 1)) + hofstadter_Q(n - hofstadter_Q(n - 2))
for i in range(100, 1000, 100):
	hofstadter_Q(i)