user
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.
        {\displaystyle {\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 **n**th term where   **n**   is large.

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

### OO solution

**Works with**: rakudo version 2016.03

Similar concept as the perl5 solution, except that the cache is only filled on demand.

```
class Hofstadter {
  has @!c = 1,1;
  method AT-POS ($me: Int $i) {
    @!c.push($me[@!c.elems-$me[@!c.elems-1]] +
	     $me[@!c.elems-$me[@!c.elems-2]]) until @!c[$i]:exists;
    return @!c[$i];
  }
}

# Testing:

my Hofstadter $Q .= new();

say "first ten: $Q[^10]";
say "1000th: $Q[999]";

my $count = 0;
$count++ if $Q[$_ +1 ] < $Q[$_] for  ^99_999;
say "In the first 100_000 terms, $count terms are less than their preceding terms";

```

Output:

```
first ten: 1 1 2 3 3 4 5 5 6 6
1000th: 502
In the first 100_000 terms, 49798 terms are less than their preceding terms
```

### Idiomatic solution

**Works with**: rakudo version 2015-11-22

With a lazily generated array, we automatically get caching.

```
my @Q = 1, 1, -> $a, $b {
    (state $n = 1)++;
    @Q[$n - $a] + @Q[$n - $b]
} ... *;

# Testing:

say "first ten: ", @Q[^10];
say "1000th: ", @Q[999];
say "In the first 100_000 terms, ",
   [+](@Q[1..100000] Z< @Q[0..99999]),
   " terms are less than their preceding terms";

```

(Same output.)