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