/* 

  Hofstadter Q sequence (Rosetta code) in Picat.

  http://rosettacode.org/wiki/Hofstadter_Q_sequence
  """
  The Hofstadter Q sequence is defined as:

        Q ( 1 ) = Q ( 2 ) = 1 , 
        Q ( n ) = Q ( n − Q ( n − 1 ) ) + Q ( n − Q ( n − 2 ) ) , n > 2. 

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


  This program was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/

% import v3_utils.
% import util.
% import cp.


main => go.

go =>
  println([ q(I) : I in 1..10]),
  println(q1000=q(1000)),
  Q = {q(I) : I in 1..100_000},
  println(flips=sum({1 : I in 2..100_000, Q[I-1] > Q[I]})),
  nl.

table
q(1) = 1.
q(2) = 1.
q(N) = q(N-q(N-1)) + q(N-q(N-2)).