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).




begin % find elements of the Hofstader Q sequence Q(1) = Q(2) = 1             %
      % Q(n) = Q( n - Q( n - 1 ) ) + Q( n - Q( n - 2 ) ) for n > 2            %
    integer MAX_Q;
    max_Q := 100000;
    begin
        integer array Q ( 1 :: MAX_Q );
        integer array xQ ( 1 :: 10 );
        integer ltCount;
        logical valuesOk;
        % expected values of the first 10 elements                            %
        xQ( 1 ) := xQ( 2 ) := 1;
        xQ( 3 ) := 2; xQ( 4 ) := xQ( 5 ) := 3; xQ( 6 ) := 4;
        xQ( 7 ) := xQ( 8 ) := 5; xQ( 9 ) := xQ( 10 ) := 6;
        % calculate the sequence and count how often Q( n ) < Q( n - 1 )      %
        ltCount := 0;
        Q( 1 ) := Q( 2 ) := 1;
        for n := 3 until MAX_Q do begin
            Q( n ) := Q( n - Q( n - 1 ) ) + Q( n - Q( n - 2 ) );
            if Q( n ) < Q( n - 1 ) then ltCount := ltCount + 1
        end for_n ;
        valuesOk := true;
        write( "The first 10 terms of the Hofstader Q sequence:" );
        for i := 1 until 10 do begin
            writeon( i_w := 1, s_w := 0, " ", Q( i ) );
            if Q( i ) not = xQ( i ) then begin
                writeon( i_w := 1, s_w := 0, "-EXPECTED-", xQ( i ) );
                valuesOk := false
            end if_Q_i_ne_xQ_i
        end for_i ;
        write( i_w := 1, s_w := 0, "The 1000th term is: ", Q( 1000 ) );
        if Q( 1000 ) not = 502 then begin
            writeon( "-EXPECTED-502" );
            valuesOk := false
        end if_Q_100_ne_502 ;
        if valuesOk then write( "    (Computed values are as expected)" )
                    else write( "Values NOT as expected" );
        write( i_w := 1, s_w := 0, "Q(n) < Q(n-1) ", ltCount," times for n up to ", MAX_Q )
    end
end.