You are encouraged to solve this task according to the task description, using any language you may know.

The Hofstadter Q sequence is defined as:

{\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.

• 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 1000'th 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,000'th 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).

## C

<lang c>#include <stdio.h>

1. include <stdlib.h>
1. define N 100000

int main() { int i, flip, *q = (int*)malloc(sizeof(int) * N) - 1;

q[1] = q[2] = 1;

for (i = 3; i <= N; i++) q[i] = q[i - q[i - 1]] + q[i - q[i - 2]];

for (i = 1; i <= 10; i++) printf("%d%c", q[i], i == 10 ? '\n' : ' ');

printf("%d\n", q[1000]);

for (flip = 0, i = 1; i < N; i++) flip += q[i] > q[i + 1];

printf("flips: %d\n", flip); return 0; }</lang>output<lang>1 1 2 3 3 4 5 5 6 6 502 flips: 49798</lang>

## C++

solution modelled after Perl solution

<lang Cpp>#include <iostream>

int main( ) {

  int hofstadters[100000] ;
hofstadters[ 0 ] = 1 ;
hofstadters[ 1 ] = 1 ;
for ( int i = 3 ; i < 100000 ; i++ )
hofstadters[ i - 1 ] = hofstadters[ i - 1 - hofstadters[ i - 1 - 1 ]] +


hofstadters[ i - 1 - hofstadters[ i - 2 - 1 ]] ;

  std::cout << "The first 10 numbers are:\n" ;
for ( int i = 0 ; i < 10 ; i++ )
std::cout << hofstadters[ i ] << std::endl ;
std::cout << "The 1000'th term is " << hofstadters[ 999 ] << " !" << std::endl ;
int less_than_preceding = 0 ;
for ( int i = 0 ; i < 99999 ; i++ ) {
if ( hofstadters[ i + 1 ] < hofstadters[ i ] )


less_than_preceding++ ;

  }
std::cout << less_than_preceding << " times a number was preceded by a greater number!\n" ;
return 0 ;


}</lang> Output:

The first 10 numbers are:
1
1
2
3
3
4
5
5
6
6
The 1000'th term is 502 !
49798 times a number was preceded by a greater number!


## C#

<lang C sharp>using System; using System.Collections.Generic;

   class Program
{
// Initialize the dictionary with the first two indices filled.
private static readonly Dictionary<int, int> QList = new Dictionary<int, int>
{
{1, 1},
{2, 1}
};

       private static void Main()
{
int lessThanLast = 0;
/* Initialize our variable that holds the number of times
* a member of the sequence was less than its preceeding term. */

           for (int n = 1; n <= 100000; n++)
{
int q = Q(n); // Get Q(n).

               if (n > 1 && QList[n - 1] > q) // If Q(n) is less than Q(n - 1),
lessThanLast++;            // then add to the counter.

               if (n > 10 && n != 1000) continue; /* If n is greater than 10 and not 1000,
* the rest of the code in the loop does not apply,
* and it will be skipped. */

               if (!Confirm(n, q)) // Confirm Q(n) is correct.
throw new Exception(string.Format("Invalid result: Q({0}) != {1}", n, q));

               Console.WriteLine("Q({0}) = {1}", n, q); // Write Q(n) to the console.
}

           Console.WriteLine("Number of times a member of the sequence was less than its preceeding term: {0}.",
lessThanLast);
}

       private static bool Confirm(int n, int value)
{
if (n <= 10)
return new[] {1, 1, 2, 3, 3, 4, 5, 5, 6, 6}[n - 1] == value;
if (n == 1000)
return 502 == value;
throw new ArgumentException("Invalid index.", "n");
}

       private static int Q(int n)
{
int q;

           if (!QList.TryGetValue(n, out q)) // Try to get Q(n) from the dictionary.
{
q = Q(n - Q(n - 1)) + Q(n - Q(n - 2)); // If it's not available, then calculate it.
}

           return q;
}
}


}</lang>

Output

Q(1) = 1
Q(2) = 1
Q(3) = 2
Q(4) = 3
Q(5) = 3
Q(6) = 4
Q(7) = 5
Q(8) = 5
Q(9) = 6
Q(10) = 6
Q(1000) = 502
Number of times a member of the sequence was less than its preceeding term: 49798.

## Common Lisp

<lang lisp>(defparameter *mm* (make-hash-table :test #'equal))

generic memoization macro

(defmacro defun-memoize (f (&rest args) &body body)

 (defmacro hash () (gethash (cons ',f (list ,@args)) *mm*))
(let ((h (gensym)))
(defun ,f (,@args)
(let ((,h (hash)))


(if ,h ,h (setf (hash) (progn ,@body)))))))

def q

(defun-memoize q (n)

 (if (<= n 2) 1
(+ (q (- n (q (- n 1))))
(q (- n (q (- n 2)))))))

test

(format t "First of Q: ~a~%Q(1000): ~a~%Bumps up to 100000: ~a~%" (loop for i from 1 to 10 collect (q i)) (q 1000) (loop with c = 0 with last-q = (q 1) for i from 2 to 100000 do (let ((next-q (q i))) (if (< next-q last-q) (incf c)) (setf last-q next-q)) finally (return c)))</lang>output<lang>First of Q: (1 1 2 3 3 4 5 5 6 6) Q(1000): 502 Bumps up to 100000: 49798</lang>

Although the above definition of q is more general, for this specific problem the following is faster:<lang lisp>(let ((cc (make-array 3 :element-type 'integer :initial-element 1 :adjustable t :fill-pointer 3)))

     (defun q (n)


(when (>= n (length cc)) (loop for i from (length cc) below n do (q i)) (vector-push-extend (+ (aref cc (- n (aref cc (- n 1)))) (aref cc (- n (aref cc (- n 2))))) cc)) (aref cc n)))</lang>

## D

<lang d>import std.stdio, std.algorithm, std.functional, std.range;

int Q(int n) {

   assert(n > 0);
alias memoize!Q mQ;
if (n == 1 || n == 2)
return 1;
else
return mQ(n - mQ(n - 1)) + mQ(n - mQ(n - 2));


}

void main() {

   writeln("Q(n) for n = [1..10] is: ", map!Q(iota(1, 11)));
writeln("Q(1000) = ", Q(1000));
writefln("Q(i) is less than Q(i-1) for i [2..100_000] %d times.",
count!((i){ return Q(i) < Q(i-1); })(iota(2, 100_001)));


}</lang> Output:

Q(n) for n = [1..10] is: [1, 1, 2, 3, 3, 4, 5, 5, 6, 6]
Q(1000) = 502
Q(i) is less than Q(i-1) for i [2..100_000] 49798 times.

### Faster version

Translation of: Python

Same output. <lang d>import std.stdio, std.algorithm, std.range, std.array;

struct Q {

   static Appender!(uint[]) s;
static this() {
s.put([0, 1, 1]);
}
static uint opCall(int n) {
assert(n > 0);
foreach (i; s.data.length .. n + 1)
s.put(s.data[i- s.data[i-1]] + s.data[i - s.data[i-2]]);
return s.data[n];
}


}

void main() {

   writeln("Q(n) for n = [1..10] is: ", map!Q(iota(1, 11)));
writeln("Q(1000) = ", Q(1000));
writefln("Q(i) is less than Q(i-1) for i [2..100_000] %d times.",
count!((i){ return Q(i) < Q(i-1); })(iota(2, 100_001)));


}</lang>

## Dart

Naive version using only recursion (Q(1000) fails due to browser script runtime restrictions) <lang dart>int Q(int n) => n>2 ? Q(n-Q(n-1))+Q(n-Q(n-2)) : 1;

main() {

 for(int i=1;i<=10;i++) {
print("Q($i)=${Q(i)}");
}
print("Q(1000)=${Q(1000)}");  }</lang> Version featuring caching. <lang dart>class Q {  Map<int,int> _table;   Q() { _table=new Map<int,int>(); _table[1]=1; _table[2]=1; }   int q(int n) { // if the cache is not filled until n-1, fill it starting with the lowest entries first // this avoids doing a recursion from n to 2 (e.g. if you call q(1000000) first) // this doesn't happen in the tasks calls since the cache is filled ascending if(_table[n-1]==null) { for(int i=_table.length;i<n;i++) {  q(i); }  } if(_table[n]==null) { _table[n]=q(n-q(n-1))+q(n-q(n-2)); }   return _table[n]; }  } main() {  Q q=new Q();   for(int i=1;i<=10;i++) { print("Q($i)=${q.q(i)}"); } print("Q(1000)=${q.q(1000)}");

 int count=0;
for(int i=2;i<=100000;i++) {
if(q.q(i)<q.q(i-1)) {
count++;
}
}
print("value is smaller than previous $count times");  }</lang> Output: Q(1)=1 Q(2)=1 Q(3)=2 Q(4)=3 Q(5)=3 Q(6)=4 Q(7)=5 Q(8)=5 Q(9)=6 Q(10)=6 Q(1000)=502 value is smaller than previous 49798 times If the maximum number is known, filling an array is probably the fastest solution. <lang dart>main() {  List<int> q=new List<int>(100001); q[1]=q[2]=1; int count=0; for(int i=3;i<q.length;i++) { q[i]=q[i-q[i-1]]+q[i-q[i-2]]; if(q[i]<q[i-1]) { count++; } } for(int i=1;i<=10;i++) { print("Q($i)=${q[i]}"); } print("Q(1000)=${q[1000]}");
print("value is smaller than previous $count times");  }</lang> ## Go Sure there are ways that run faster or handle larger numbers; for the task though, maps and recursion work just fine. <lang go>package main import "fmt" var m map[int]int func initMap() {  m = make(map[int]int) m[1] = 1 m[2] = 1  } func q(n int) (r int) {  if r = m[n]; r == 0 { r = q(n-q(n-1)) + q(n-q(n-2)) m[n] = r } return  } func main() {  initMap() // task for n := 1; n <= 10; n++ { showQ(n) } // task showQ(1000) // extra credit count, p := 0, 1 for n := 2; n <= 1e5; n++ { qn := q(n) if qn < p { count++ } p = qn } fmt.Println("count:", count) // extra credit initMap() showQ(1e6)  } func showQ(n int) {  fmt.Printf("Q(%d) = %d\n", n, q(n))  }</lang> Output: Q(1) = 1 Q(2) = 1 Q(3) = 2 Q(4) = 3 Q(5) = 3 Q(6) = 4 Q(7) = 5 Q(8) = 5 Q(9) = 6 Q(10) = 6 Q(1000) = 502 count: 49798 Q(1000000) = 512066  ## Haskell Data.MemoTrie is not installed by default. <lang Haskell>import Data.MemoTrie(memo) {- cabal install memotrie -} q :: Int -> Int q = memo q' where  q' 1 = 1 q' 2 = 1 q' n = q (n - q (n - 1)) + q (n - q (n - 2))</lang>  ## Icon and Unicon <lang Icon>link printf procedure main() V := [1, 1, 2, 3, 3, 4, 5, 5, 6, 6] every i := 1 to *V do  if Q(i) ~= V[i] then stop("Assertion failure for position ",i)  printf("Q(1 to %d) - verified.\n",*V) q := Q(n := 1000) v := 502 printf("Q[%d]=%d - %s.\n",n,v,if q = v then "verified" else "failed") invcount := 0 every i := 2 to (n := 100000) do  if Q(i) < Q(i-1) then { printf("Q(%d)=%d < Q(%d)=%d\n",i,Q(i),i-1,Q(i-1)) invcount +:= 1 }  printf("There were %d inversions in Q up to %d\n",invcount,n) end procedure Q(n) #: Hofstader Q sequence static S initial S := [1,1] if q := S[n] then return q else {  q := Q(n - Q(n - 1)) + Q(n - Q(n - 2)) if *S = n - 1 then { put(S,q) return q } else runerr(500,n) }  end</lang> Output: Q(1 to 10) - verified. Q[1000]=502 - verified. Q(16)=9 < Q(15)=10 Q(25)=14 < Q(24)=16 Q(32)=17 < Q(31)=20 Q(36)=19 < Q(35)=21 ... Q(99996)=48252 < Q(99995)=50276 Q(99999)=48456 < Q(99998)=50901 Q(100000)=48157 < Q(99999)=48456 There were 49798 inversions in Q up to 100000 ## J <lang j>Qs=:0 1 1 Q=: verb define  n=. >./,y while. n>:#Qs do. Qs=: Qs,+/((#Qs)-_2{.Qs){Qs end. y{Qs  )</lang> Examples: <lang j> Q 1+i.10 1 1 2 3 3 4 5 5 6 6  Q 1000  502  +/2>/\ Q 1+i.100000  49798</lang> ## Java Works with: Java version 1.5+ This example also counts the number of times each n is used as an argument up to 100000 and reports the one that was used the most. <lang java5>import java.util.HashMap; import java.util.Map; public class HofQ { private static Map<Integer, Integer> q = new HashMap<Integer, Integer>(){{ put(1, 1); put(2, 1); }}; private static int[] nUses = new int[100001];//not part of the task public static int Q(int n){ nUses[n]++;//not part of the task if(q.containsKey(n)){ return q.get(n); } int ans = Q(n - Q(n - 1)) + Q(n - Q(n - 2)); q.put(n, ans); return ans; } public static void main(String[] args){ for(int i = 1; i <= 10; i++){ System.out.println("Q(" + i + ") = " + Q(i)); } int last = 6;//value for Q(10) int count = 0; for(int i = 11; i <= 100000; i++){ int curr = Q(i); if(curr < last) count++; last = curr; if(i == 1000) System.out.println("Q(1000) = " + curr); } System.out.println("Q(i) is less than Q(i-1) for i <= 100000 " + count + " times"); //Optional stuff below here int maxUses = 0, maxN = 0; for(int i = 1; i<nUses.length;i++){ if(nUses[i] > maxUses){ maxUses = nUses[i]; maxN = i; } } System.out.println("Q(" + maxN + ") was called the most with " + maxUses + " calls"); } }</lang> Output: Q(1) = 1 Q(2) = 1 Q(3) = 2 Q(4) = 3 Q(5) = 3 Q(6) = 4 Q(7) = 5 Q(8) = 5 Q(9) = 6 Q(10) = 6 Q(1000) = 502 Q(i) is less than Q(i-1) for i <= 100000 49798 times Q(44710) was called the most with 19 calls ## Perl <lang Perl>#!/usr/bin/perl -w use strict ; my @hofstadters = ( 1 , 1 ) ; while ( @hofstadters < 100000 ) {  my$nextn = scalar @hofstadters + 1 ;

1. array index counting starts at 0 , so we have to subtract 1 from the numbers!
  push @hofstadters ,  $hofstadters [$nextn - 1 - $hofstadters[$nextn - 1 - 1 ] ]
+ $hofstadters[$nextn - 1 - $hofstadters[$nextn - 2 - 1 ]]   ;


} for my $i ( 0..9 ) {  print "$hofstadters[ $i ]\n" ;  } print "The 1000'th term is$hofstadters[ 999 ]!\n" ; my $less_than_preceding = 0 ; for my$i ( 0..99998 ) {

  $less_than_preceding++ if$hofstadters[ $i + 1 ] <$hofstadters[ $i ] ;  } print "Up to and including the 100000'th term,$less_than_preceding terms are less " .

  "than their preceding terms!\n" ;


</lang> Output:

1
1
2
3
3
4
5
5
6
6
The 1000'th term is 502!
Up to and including the 100000'th term, 49798 terms are less than their preceding terms!


## PicoLisp

<lang PicoLisp>(de q (N)

  (cache '(NIL) (pack (char (hash N)) N)
(if (>= 2 N)
1
(+
(q (- N (q (dec N))))
(q (- N (q (- N 2)))) ) ) ) )</lang>


Test: <lang PicoLisp>: (mapcar q (range 1 10)) -> (1 1 2 3 3 4 5 5 6 6)

(q 1000)

-> 502

(let L (mapcar q (range 1 100000))
  (cnt < (cdr L) L) )


-> 49798</lang>

## Python

<lang python>def q(n):

   if n < 1 or type(n) != int: raise ValueError("n must be an int >= 1")
try:
return q.seq[n]
except IndexError:
ans = q(n - q(n - 1)) + q(n - q(n - 2))
q.seq.append(ans)
return ans


q.seq = [None, 1, 1]

if __name__ == '__main__':

   first10 = [q(i) for i in range(1,11)]
assert first10 == [1, 1, 2, 3, 3, 4, 5, 5, 6, 6], "Q() value error(s)"
print("Q(n) for n = [1..10] is:", ', '.join(str(i) for i in first10))
assert q(1000) == 502, "Q(1000) value error"
print("Q(1000) =", q(1000))</lang>

Extra credit

If you try and initially compute larger values of n then you tend to hit the Python recursion limit.

The function q1 gets around this by calling function q to extend the Q series in increments below the recursion limit.

The following code is to be concatenated to the code above: <lang python>from sys import getrecursionlimit

def q1(n):

   if n < 1 or type(n) != int: raise ValueError("n must be an int >= 1")
try:
return q.seq[n]
except IndexError:
len_q, rlimit = len(q.seq), getrecursionlimit()
if (n - len_q) > (rlimit // 5):
for i in range(len_q, n, rlimit // 5):
q(i)
ans = q(n - q(n - 1)) + q(n - q(n - 2))
q.seq.append(ans)
return ans


if __name__ == '__main__':

   tmp = q1(100000)
print("Q(i+1) < Q(i) for i [1..100000] is true %i times." %
sum(k1 < k0 for k0, k1 in zip(q.seq[1:], q.seq[2:])))</lang>

Combined output
Q(n) for n = [1..10] is: 1, 1, 2, 3, 3, 4, 5, 5, 6, 6
Q(1000) = 502
Q(i+1) < Q(i) for i [1..10000] is true 49798 times.

### Alternative

<lang python>def q(n):

   l = len(q.seq)
while l <= n:
q.seq.append(q.seq[l - q.seq[l - 1]] + q.seq[l - q.seq[l - 2]])


l += 1

   return q.seq[n]


q.seq = [None, 1, 1]

print("Q(n) for n = [1..10] is:", [q(i) for i in range(1, 11)]) print("Q(1000) =", q(1000)) q(100000) print("Q(i+1) < Q(i) for i [1..100000] is true %i times." %

     sum([q.seq[i] > q.seq[i + 1] for i in range(1, 100000)]))</lang>


## Ruby

<lang ruby>@cache = [] def Q(n)

 if @cache[n].nil?
case n
when 1, 2 then @cache[n] = 1
else @cache[n] = Q(n - Q(n-1)) + Q(n - Q(n-2))
end
end
@cache[n]


end

puts "first 10 numbers in the sequence: #{1.upto(10).map {|n| Q(n)}}" puts "1000'th term: #{Q(1000)}"

prev = Q(1) count = 0 2.upto(100_000) do |n|

 q = Q(n)
count += 1 if q < prev
prev = q


end puts "number of times in the first 100,000 terms where Q(i)<Q(i-1): #{count}"</lang> output

first 10 numbers in the sequence: [1, 1, 2, 3, 3, 4, 5, 5, 6, 6]
1000'th term: 502
number of times in the first 100,000 terms where Q(i)<Q(i-1): 49798

## Scheme

I wish there were a portable way to define-syntax, or to resize arrays, or to do formated output--anything to make the code less silly looking while still run under more than one interpreter. <lang lisp>(define qc '#(0 1 1)) (define filled 3) (define len 3)

chicken scheme
vector-resize!
gambit
vector-append

(define (extend-qc)

 (let* ((new-len (* 2 len))


(new-qc (make-vector new-len)))

   (let copy ((n 0))
(if (< n len)


(begin (vector-set! new-qc n (vector-ref qc n)) (copy (+ 1 n)))))

   (set! len new-len)
(set! qc new-qc)))


(define (q n)

 (let loop ()
(if (>= filled len) (extend-qc))
(if (>= n filled)
(begin


(vector-set! qc filled (+ (q (- filled (q (- filled 1)))) (q (- filled (q (- filled 2)))))) (set! filled (+ 1 filled)) (loop))

     (vector-ref qc n))))


(display "Q(1 .. 10): ") (let loop ((i 1))

 ;; (print) behave differently regarding newline across compilers
(display (q i))
(display " ")
(if (< i 10)
(loop (+ 1 i))
(newline)))


(display "Q(1000): ") (display (q 1000)) (newline)

(display "bumps up to 100000: ") (display

 (let loop ((s 0) (i 1))
(if (>= i 100000) s
(loop (+ s (if (> (q i) (q (+ 1 i))) 1 0)) (+ 1 i)))))


(newline)</lang>output<lang>Q(1 .. 10): 1 1 2 3 3 4 5 5 6 6 Q(1000): 502 bumps up to 100000: 49798</lang>

<lang seed7>$include "seed7_05.s7i"; const type: intHash is hash [integer] integer; var intHash: qHash is intHash.value; const func integer: q (in integer: n) is func  result var integer: q is 1; begin if n in qHash then q := qHash[n]; else if n > 2 then q := q(n - q(pred(n))) + q(n - q(n - 2)); end if; qHash @:= [n] q; end if; end func;  const proc: main is func  local var integer: n is 0; var integer: less_than_preceding is 0; begin writeln("q(n) for n = 1 .. 10:"); for n range 1 to 10 do write(q(n) <& " "); end for; writeln; writeln("q(1000)=" <& q(1000)); for n range 2 to 100000 do if q(n) < q(pred(n)) then incr(less_than_preceding); end if; end for; writeln("q(n) < q(n-1) for n = 2 .. 100000: " <& less_than_preceding); end func;</lang>  Output: q(n) for n = 1 .. 10: 1 1 2 3 3 4 5 5 6 6 q(1000)=502 q(n) < q(n-1) for n = 2 .. 100000: 49798  ## Tcl <lang tcl>package require Tcl 8.5 1. Index 0 is not used, but putting it in makes the code a bit shorter set tcl::mathfunc::Qcache {Q:-> 1 1} proc tcl::mathfunc::Q {n} {  variable Qcache if {$n >= [llength $Qcache]} {  lappend Qcache [expr {Q($n - Q($n-1)) + Q($n - Q($n-2))}]  } return [lindex$Qcache $n]  } 1. Demonstration code for {set i 1} {$i <= 10} {incr i} {

   puts "Q($i) == [expr {Q($i)}]"


}

1. This runs very close to recursion limit...

puts "Q(1000) == [expr Q(1000)]"

1. This code is OK, because the calculations are done step by step

set q [expr Q(1)] for {set i 2} {$i <= 100000} {incr i} {  incr count [expr {$q > [set q [expr {Q($i)}]]}]  } puts "Q(i)<Q(i-1) for i $2..100000$ is true$count times"</lang> Output:

Q(1) == 1
Q(2) == 1
Q(3) == 2
Q(4) == 3
Q(5) == 3
Q(6) == 4
Q(7) == 5
Q(8) == 5
Q(9) == 6
Q(10) == 6
Q(1000) == 502
Q(i)<Q(i-1) for i [2..100000] is true 49798 times