How to resolve the algorithm Hofstadter Q sequence step by step in the Oberon-2 programming language

Published on 12 May 2024 09:40 PM
#Oberon-2

How to resolve the algorithm Hofstadter Q sequence step by step in the Oberon-2 programming language

Table of Contents

Problem Statement

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.

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

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Hofstadter Q sequence step by step in the Oberon-2 programming language

Source code in the oberon-2 programming language

MODULE Hofstadter;
IMPORT 
  Out;
  
VAR
  i,count,q,prev: LONGINT; 
  founds: ARRAY 100001 OF LONGINT;
  
  PROCEDURE Q(n: LONGINT): LONGINT;
  BEGIN
    IF founds[n] = 0 THEN
      CASE n OF
        1 .. 2: 
            founds[n] := 1
        ELSE  founds[n] := Q(n - Q(n - 1)) + Q(n - Q(n - 2))  
      END
    END;
    RETURN founds[n]
  END Q;
  
BEGIN
  (* first ten numbers in the sequence *)
  FOR i := 1 TO 10 DO
    Out.String("At ");Out.LongInt(i,0);Out.String(":> ");Out.LongInt(Q(i),4);Out.Ln
  END;
  
  Out.String("1000th value: ");Out.LongInt(Q(1000),4);Out.Ln;
  
  prev := 1;
  FOR i := 2 TO 100000 DO
    q := Q(i);
    IF q < prev THEN INC(count) END;
    prev := q
  END;
  Out.String("terms less than the previous: ");Out.LongInt(count,4);Out.Ln
END Hofstadter.

You may also check:How to resolve the algorithm Find if a point is within a triangle step by step in the XPL0 programming language
You may also check:How to resolve the algorithm Memory layout of a data structure step by step in the Free Pascal programming language
You may also check:How to resolve the algorithm Assertions step by step in the zkl programming language
You may also check:How to resolve the algorithm Roots of a function step by step in the Scheme programming language
You may also check:How to resolve the algorithm Count in octal step by step in the Standard ML programming language