Hofstadter Q sequence


 







Q
(
1
)



=
Q
(
2
)
=
1
,




Q
(
n
)



=
Q


(


n
−
Q
(
n
−
1
)


)


+
Q


(


n
−
Q
(
n
−
2
)


)


,

n
>
2.






{\displaystyle {\begin{aligned}Q(1)&=Q(2)=1,\\Q(n)&=Q{\big (}n-Q(n-1){\big )}+Q{\big (}n-Q(n-2){\big )},\quad n>2.\end{aligned}}}




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 1000th term is:   502


Optional extra credit
 Count and display how many times a member of the sequence is less than its preceding term for terms up to and including the 100,000th term.
 Ensure that the extra credit solution   safely   handles being initially asked for an nth term where   n   is large.

(This point is to ensure that caching and/or recursion limits, if it is a concern, is correctly handled).




code ChOut=8, CrLf=9, IntOut=11;
int  N, C, Q(100_001);
[Q(1):= 1;  Q(2):= 1;  C:= 0;
for N:= 3 to 100_000 do
        [Q(N):= Q(N-Q(N-1)) + Q(N-Q(N-2));
        if Q(N) < Q(N-1) then C:= C+1;
        ];
for N:= 1 to 10 do
        [IntOut(0, Q(N));  ChOut(0, ^ )];
CrLf(0);
IntOut(0, Q(1000));  CrLf(0);
IntOut(0, C);  CrLf(0);
]