Hofstadter Q sequence

From Fōrmulæ wiki
Revision as of 15:39, 26 July 2019 by Admin (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

This page is the answer to the task Hofstadter Q sequence in the Rosetta Code.

Description (from Rosetta Code)

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

Solution

The following script defines a function to create a list with the first n terms of the sequence.

HofstadterQCode.png

Case 1. First ten terms

HofstadterQCase1.png

Case 2. 1000th term

The x list is created containing the first 1000,000 terms. It will be used for this case and the next one:

HofstadterQCase2.png

Obtaining the 1000th term:

HofstadterQCase2a.png

Case 3. Extra credit

The following script counts how many times a member of the x list is less than its preceding term:

HofstadterQCase3.png