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




with Ada.Text_IO;
 
procedure Hofstadter_Q_Sequence is
 
   type Callback is access procedure(N: Positive);
 
   procedure Q(First, Last: Positive; Q_Proc: Callback) is
   -- calls Q_Proc(Q(First)); Q_Proc(Q(First+1)); ... Q_Proc(Q(Last));
   -- precondition: Last > 2
 
      Q_Store: array(1 .. Last) of Natural := (1 => 1, 2 => 1, others => 0);
      -- "global" array to store the Q(I)
      -- if Q_Store(I)=0, we compute Q(I) and update Q_Store(I)
      -- else we already know Q(I) = Q_Store(I)
 
      function Q(N: Positive) return Positive is
      begin
         if Q_Store(N) = 0 then
            Q_Store(N) := Q(N - Q(N-1)) + Q(N-Q(N-2));
         end if;
         return Q_Store(N);
      end Q;
 
   begin
      for I in First .. Last loop
         Q_Proc(Q(I));
      end loop;
   end Q;
 
   procedure Print(P: Positive) is
   begin
      Ada.Text_IO.Put(Positive'Image(P));
   end Print;
 
   Decrease_Counter: Natural := 0;
   Previous_Value: Positive := 1;
 
   procedure Decrease_Count(P: Positive) is
   begin
      if P < Previous_Value then
         Decrease_Counter := Decrease_Counter + 1;
      end if;
      Previous_Value := P;
   end Decrease_Count;
 
begin
   Q(1, 10, Print'Access);
   -- the first ten terms of the sequence are: 1, 1, 2, 3, 3, 4, 5, 5, 6, and 6
   Ada.Text_IO.New_Line;
 
   Q(1000, 1000,  Print'Access);
   -- the 1000'th term is: 502
   Ada.Text_IO.New_Line;
 
   Q(2, 100_000, Decrease_Count'Access);
   Ada.Text_IO.Put_Line(Integer'Image(Decrease_Counter));
   -- how many times a member of the sequence is less than its preceding term
   -- for terms up to and including the 100,000'th term
end Hofstadter_Q_Sequence;