Hofstadter Q sequence: Difference between revisions

{{task}}The [[wp:Hofstadter_sequence#Hofstadter_Q_sequence|Hofstadter Q sequence]] is defined as:

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{align}</math>

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

 

;Optional extra credit

 

=={{header|C}}==

#include <stdlib.h>

 

printf("flips: %d\n", flip);

return 0;

502

</pre>

 

=={{header|C sharp}}==

 

using System.Collections.Generic;

 

int lessThanLast = 0;

/* Initialize our variable that holds the number of times

 

for (int n = 1; n <= 100000; n++)

}

 

lessThanLast);

}

}

}

 

<pre>Q(1) = 1

Q(2) = 1

Q(10) = 6

Q(1000) = 502

 

=={{header|Common Lisp}}==

 

;;; generic memoization macro

(if (< next-q last-q) (incf c))

(setf last-q next-q))

Q(1000): 502

 

:initial-element 1

:adjustable t

(aref cc (- n (aref cc (- n 2)))))

cc))

 

=={{header|D}}==

 

assert(n > 0);

if (n == 1 || n == 2)

return 1;

 

void main() {

writeln("Q(1000) = ", Q(1000));

writefln("Q(i) is less than Q(i-1) for i [2..100_000] %d times.",

<pre>Q(n) for n = [1..10] is: [1, 1, 2, 3, 3, 4, 5, 5, 6, 6]

Q(1000) = 502

{{trans|Python}}

Same output.

 

}

 

void main() {

writeln("Q(1000) = ", Q(1000));

writefln("Q(i) is less than Q(i-1) for i [2..100_000] %d times.",

 

=={{header|Dart}}==

Naive version using only recursion (Q(1000) fails due to browser script runtime restrictions)

 

main() {

}

print("Q(1000)=${Q(1000)}");

 

Version featuring caching.

Map<int,int> _table;

 

}

print("value is smaller than previous $count times");

<pre>Q(1)=1

Q(2)=1

 

If the maximum number is known, filling an array is probably the fastest solution.

List<int> q=new List<int>(100001);

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

print("Q(1000)=${q[1000]}");

print("value is smaller than previous $count times");

=={{header|Go}}==

Sure there are ways that run faster or handle larger numbers; for the task though, maps and recursion work just fine.

 

import "fmt"

func showQ(n int) {

fmt.Printf("Q(%d) = %d\n", n, q(n))

<pre>

Q(1) = 1

Q(1000000) = 512066

</pre>

 

=={{header|Haskell}}==

 

 

 

=={{header|Icon}} and {{header|Unicon}}==

 

procedure main()

runerr(500,n)

}

 

{{libheader|Icon Programming Library}}

[http://www.cs.arizona.edu/icon/library/src/procs/printf.icn printf.icn provides formatting]

 

Q[1000]=502 - verified.

Q(16)=9 < Q(15)=10

There were 49798 inversions in Q up to 100000</pre>

 

 

=={{header|J}}==

 

 

1 1 2 3 3 4 5 5 6 6

Q 1000

502

+/2>/\ Q 1+i.100000

=={{header|Java}}==

[[Category:Memoization]]{{works with|Java|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.

import java.util.Map;

 

System.out.println("Q(" + maxN + ") was called the most with " + maxUses + " calls");

}

<pre>Q(1) = 1

Q(2) = 1

Q(i) is less than Q(i-1) for i <= 100000 49798 times

Q(44710) was called the most with 19 calls</pre>

 

=={{header|Perl}}==

 

while ( @hofstadters < 100000 ) {

push @hofstadters , $hofstadters [ $nextn - 1 - $hofstadters[ $nextn - 1 - 1 ] ]

}

for my $i ( 0..9 ) {

}

for my $i ( 0..99998 ) {

}

print "Up to and including the 100000'th term, $less_than_preceding terms are less " .

<pre>1

1

Up to and including the 100000'th term, 49798 terms are less than their preceding terms!

</pre>

 

=={{header|PicoLisp}}==

(if (>= 2 N)

1

(+

(q (- N (q (dec N))))

Test:

-> (1 1 2 3 3 4 5 5 6 6)

 

: (let L (mapcar q (range 1 100000))

(cnt < (cdr L) L) )

 

=={{header|Python}}==

if n < 1 or type(n) != int: raise ValueError("n must be an int >= 1")

try:

print("Q(n) for n = [1..10] is:", ', '.join(str(i) for i in first10))

assert q(1000) == 502, "Q(1000) value error"

 

;Extra credit:

 

The following code is to be concatenated to the code above:

 

def q1(n):

tmp = q1(100000)

print("Q(i+1) < Q(i) for i [1..100000] is true %i times." %

 

<pre>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.</pre>

===Alternative===

l = len(q.seq)

while l <= n:

q(100000)

print("Q(i+1) < Q(i) for i [1..100000] is true %i times." %

 

=={{header|Ruby}}==

def Q(n)

if @cache[n].nil?

end

 

puts "1000'th term: #{Q(1000)}"

 

prev = q

end

<pre>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</pre>

 

=={{header|Scheme}}==

(define filled 3)

(define len 3)

(if (>= i 100000) s

(loop (+ s (if (> (q i) (q (+ 1 i))) 1 0)) (+ 1 i)))))

Q(1000): 502

 

=={{header|Seed7}}==

 

const type: intHash is hash [integer] integer;

end for;

writeln("q(n) < q(n-1) for n = 2 .. 100000: " <& less_than_preceding);

 

<pre>

q(n) for n = 1 .. 10:

q(1000)=502

q(n) < q(n-1) for n = 2 .. 100000: 49798

</pre>

 

=={{header|Tcl}}==

 

# Index 0 is not used, but putting it in makes the code a bit shorter

incr count [expr {$q > [set q [expr {Q($i)}]]}]

}

<pre>

Q(1) == 1

Q(i)<Q(i-1) for i [2..100000] is true 49798 times

</pre>