Hofstadter Q sequence
The Hofstadter Q sequence is defined as:
It is defined like the Fibonacci sequence, but whereas the next term in the Fibonacci sequence is the sum of the previous two terms, in the Q sequence the previous two terms tell you how far to go back in the Q sequence to find the two numbers to sum to make the next term of the sequence.
- Task
- Confirm and display that the first ten terms of the sequence are: 1, 1, 2, 3, 3, 4, 5, 5, 6, and 6
- Confirm and display that the 1000'th term is: 502
- Optional extra credit
- Count and display how many times a member of the sequence is less than its preceeding term for terms up to and including the 100,000'th term.
Python
<lang python>def q(n):
if n < 1 or type(n) != int: raise ValueError("n must be an int >= 1") try: return q.seq[n] except IndexError: ans = q(n - q(n - 1)) + q(n - q(n - 2)) q.seq.append(ans) return ans
q.seq = [None, 1, 1]
if __name__ == '__main__':
first10 = [q(i) for i in range(1,11)] assert first10 == [1, 1, 2, 3, 3, 4, 5, 5, 6, 6], "Q() value error(s)" print("Q(n) for n = [1..10] is:", ', '.join(str(i) for i in first10)) assert q(1000) == 502, "Q(1000) value error" print("Q(1000) =", q(1000))</lang>
- Extra credit
If you try and initially compute larger values of n then you tend to hit the Python recursion limit.
The function q1 gets around this by calling function q to extend the Q series in increments below the recursion limit.
The following code is to be concatenated to the code above: <lang python>from sys import getrecursionlimit
def q1(n):
if n < 1 or type(n) != int: raise ValueError("n must be an int >= 1") try: return q.seq[n] except IndexError: len_q, rlimit = len(q.seq), getrecursionlimit() if (n - len_q) > (rlimit // 5): for i in range(len_q, n, rlimit // 5): q(i) ans = q(n - q(n - 1)) + q(n - q(n - 2)) q.seq.append(ans) return ans
if __name__ == '__main__':
tmp = q1(100000) print("Q(i+1) < Q(i) for i [1..10000] is true %i times." % sum(k1 < k0 for k0, k1 in zip(q.seq[1:], q.seq[2:])))</lang>
- Combined output
Q(n) for n = [1..10] is: 1, 1, 2, 3, 3, 4, 5, 5, 6, 6 Q(1000) = 502 Q(i+1) < Q(i) for i [1..10000] is true 49798 times.