Hofstadter Q sequence: Difference between revisions

From Rosetta Code
Content added Content deleted
(perl6 solution added)
Line 695: Line 695:
</pre>
</pre>


=={{header|Perl 6}}==
Similar concept as the perl5 solution, except that the cache is only filled on demand.

<lang Perl6>
class Hofstadter{
has @!c = 1,1;
multi method postcircumfix:<[ ]> ($me: Int $i){
@!c.push($me[@!c.elems-$me[@!c.elems-1]] +
$me[@!c.elems-$me[@!c.elems-2]])until @!c.exists($i);
return @!c[$i];
}

# note that this method isn't strictly required for solving the task,
# it's just a wrapper to get more than one item
multi method postcircumfix:<[ ]> ($me: Range $is){
return gather {take $me[$_] for $is.iterator;}
}
}

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 preceeding terms";
</lang>

Output:

<pre>
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 preceeding terms
</pre>
=={{header|PicoLisp}}==
=={{header|PicoLisp}}==
<lang PicoLisp>(de q (N)
<lang PicoLisp>(de q (N)

Revision as of 18:43, 20 November 2011

Task
Hofstadter Q sequence
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:

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

Ada

<lang Ada>with Ada.Text_IO;

procedure Hofstadter_Q_Sequence is 

  type Callback is access procedure(N: Positive);

  procedure Q(First, Last: Positive; Q_Proc: Callback) is
  -- calls Q_Proc(Q(First)); Q_Proc(Q(First+1)); ... Q_Proc(Q(Last));
  -- precondition: Last > 2

     Q_Store: array(1 .. Last) of Natural := (1 => 1, 2 => 1, others => 0);
     -- "global" array to store the Q(I)
     -- if Q_Store(I)=0, we compute Q(I) and update Q_Store(I)
     -- else we already know Q(I) = Q_Store(I)

     function Q(N: Positive) return Positive is
     begin
        if Q_Store(N) = 0 then
           Q_Store(N) := Q(N - Q(N-1)) + Q(N-Q(N-2));
        end if;
        return Q_Store(N);
     end Q;

  begin
     for I in First .. Last loop
        Q_Proc(Q(I));
     end loop;
  end Q;

  procedure Print(P: Positive) is
  begin
     Ada.Text_IO.Put(Positive'Image(P));
  end Print;

  Decrease_Counter: Natural := 0;
  Previous_Value: Positive := 1;

  procedure Decrease_Count(P: Positive) is
  begin
     if P < Previous_Value then
        Decrease_Counter := Decrease_Counter + 1;
     end if;
     Previous_Value := P;
  end Decrease_Count;

begin 

  Q(1, 10, Print'Access);
  -- the first ten terms of the sequence are: 1, 1, 2, 3, 3, 4, 5, 5, 6, and 6
  Ada.Text_IO.New_Line;

  Q(1000, 1000,  Print'Access);
  -- the 1000'th term is: 502
  Ada.Text_IO.New_Line;

  Q(2, 100_000, Decrease_Count'Access);
  Ada.Text_IO.Put_Line(Integer'Image(Decrease_Counter));
  -- 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

end Hofstadter_Q_Sequence;</lang>

Output: 

 1 1 2 3 3 4 5 5 6 6
 502
 49798

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;

namespace HofstadterQSequence { 

   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.
               QList.Add(n, q); // Add it to the dictionary.
           }

           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

<lang Haskell>import Data.Array

qSequence n = arr 

 where
    arr = array (1,n) $ (1,1):(2,1):[(i, g i) | i <- [3..n]] 
    g n = arr!(n - arr!(n-1)) + 
          arr!(n - arr!(n-2))

gradualth m k arr -- gradually precalculate m-th item 

       | m <= v = pre `seq` arr!m        --   in steps of k
 where                                   --     to prevent STACK OVERFLOW 
   pre = foldl1 (\a b-> a `seq` arr!b) [u,u+k..m]
   (u,v) = bounds arr

qSeqTest m k n = let arr = qSequence $ max m n in 

 ( gradualth m k    $ arr                      -- m-th item
 , take 10 . elems  $ arr                      -- 10 first items
 , length . filter (> 0)                       -- reversals in n items
    . _S (zipWith (-)) tail . take n . elems $ arr
 )

_S f g x = f x (g x)</lang>

Output:

<lang Haskell>Prelude Main> qSeqTest 1000 1000 100000 (502,[1,1,2,3,3,4,5,5,6,6],49798) (0.09 secs, 18879708 bytes)

Prelude Main> qSeqTest 1000000 1000000 100000 (*** Exception: stack overflow

Prelude Main> qSeqTest 1000000 10000 100000 (512066,[1,1,2,3,3,4,5,5,6,6],49798) (2.80 secs, 87559640 bytes)</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>

Library: Icon Programming Library

printf.icn provides formatting

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

PARI/GP

This example does not show the output mentioned in the task description on this page (or a page linked to from here). Please ensure that it meets all task requirements and remove this message.
Note that phrases in task descriptions such as "print and display" and "print and show" for example, indicate that (reasonable length) output be a part of a language's solution.


Straightforward, unoptimized version; about 1 ms. <lang parigp>Q=vector(1000);Q[1]=Q[2]=1;for(n=3,#Q,Q[n]=Q[n-Q[n-1]]+Q[n-Q[n-2]]); Q1=vecextract(Q,"1..10"); print("First 10 terms: "Q1,if(Q1==[1, 1, 2, 3, 3, 4, 5, 5, 6, 6]," (as expected)"," (in error)")); print("1000-th term: "Q[1000],if(Q[1000]==502," (as expected)"," (in error)"));</lang>

Perl

<lang Perl>#!/usr/bin/perl use warnings; use strict;

my @hofstadters = ( 1 , 1 ); while ( @hofstadters < 100000 ) { 

  my $nextn = @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!

Perl 6

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

<lang Perl6> class Hofstadter{ 

 has @!c = 1,1;
 multi method postcircumfix:<[ ]> ($me: Int $i){
   @!c.push($me[@!c.elems-$me[@!c.elems-1]] +

$me[@!c.elems-$me[@!c.elems-2]])until @!c.exists($i); 

   return @!c[$i];
 }

 # note that this method isn't strictly required for solving the task,
 # it's just a wrapper to get more than one item
 multi method postcircumfix:<[ ]> ($me: Range $is){
   return gather {take $me[$_] for $is.iterator;}
 }

}

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 preceeding terms"; </lang>

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 preceeding 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>

Seed7

<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
Retrieved from "https://rosettacode.org/wiki/Hofstadter_Q_sequence?oldid=203457"