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|360 Assembly}}==

{{trans|PL/I}}

HOFSTRAD CSECT

USING HOFSTRAD,R15 set base register

Q DS 1000F array q(1000)

YREGS

{{out}}

<pre style="height:16ex">

n= 10, q= 6

n=1000, q= 502

</pre>

 

=={{header|Ada}}==

 

procedure Hofstadter_Q_Sequence is

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

 

{{out}}

{{wont work with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d] - due to extensive use of '''format'''[ted] ''transput''.}}

 

 

INT n = 100000;

 

printf(($"flips: "g(0)l$, flip))

{{out}}

<pre>

flips: 49798

</pre>

 

=={{header|AutoHotkey}}==

Q := HofsQSeq(100000)

 

}

return Q

{{out}}

<pre>First ten: 1, 1, 2, 3, 3, 4, 5, 5, 6, 6,

 

=={{header|AWK}}==

BEGIN {

N = 100000

}

return seq

 

<pre>Q-sequence(1..10) : 1 1 2 3 3 4 5 5 6 6

number of Q(n)<Q(n+1) for n<=100000 : 49798</pre>

 

FOR i% = 1 TO 10 : PRINT ;FNq(i%, c%) " "; : NEXT : PRINT

PRINT "1000th term = " ; FNq(1000, c%)

IF q%(i%) < q%(i%-1) THEN c% += 1

NEXT

{{out}}

<pre>

Term is less than preceding term 49798 times

</pre>

 

=={{header|Bracmat}}==

& tbl$(memo,!memocells+1) { allocate array }

& ( Q

)

& out$!lessThan

Output:

<pre>1 1 2 3 3 4 5 5 6 6

502

49798</pre>

 

=={{header|C}}==

#include <stdlib.h>

 

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

return 0;

{{out}}

<pre>1 1 2 3 3 4 5 5 6 6

flips: 49798

</pre>

 

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

 

using System.Collections.Generic;

 

}

}

 

{{out}}

Q(1000) = 502

Number of times a member of the sequence was less than its preceding term: 49798.</pre>

 

=={{header|Clojure}}==

The subsequences are vectors for efficient indexing.

''qfirst'' iterates ''qs'' so the nth iteration is Q{1..n].

(let [n (count q)]

(condp = n

(println "first 10:" (qfirst 10))

(println "1000th:" (last (qfirst 1000)))

{{out}}

1000th: 502

 

=={{header|CoffeeScript}}==

{{trans|JavaScript}}

memo = [ 1 ,1, 1]

Q = (n) ->

# some results:

console.log 'Q(' + i + ') = ' + hofstadterQ(i) for i in [1..10]

{{out}}

<pre>Q(1) = 1

Q(9) = 6

Q(10) = 6

Q(1000) = 502</pre>

 

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

 

;;; generic memoization macro

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

(setf last-q next-q))

{{out}}

<pre>First of Q: (1 1 2 3 3 4 5 5 6 6)

Bumps up to 100000: 49798</pre>

 

:initial-element 1

:adjustable t

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

cc))

 

=={{header|D}}==

 

int Q(in int n) nothrow

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

iota(2, 100_001).count!(i => Q(i) < Q(i - 1)));

{{out}}

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

Q(1000) = 502

 

===Faster Version===

{{trans|Python}}

Same output.

 

uint Q(in int n) nothrow

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

iota(2, 100_001).count!(i => Q(i) < Q(i - 1)));

 

===Even Faster Version===

This code is here to show that you don't have to use all fancy features of D. Straightforward simple code is often clearer, and faster.

 

import std.stdio;

 

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

}

 

=={{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");

{{out}}

<pre>Q(1)=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|EchoLisp}}==

(define RECURSE_BUMP 500) ;; minimum of chrome:500 safari:1000 firefox:2000

 

(Q 1000) → 502

(flips 100000) → 49798

 

=={{header|Eiffel}}==

class

APPLICATION

end

 

{{out}}

<pre>

Number of Flips:

49798

</pre>

 

=={{header|Erlang}}==

%% Hofstadter Q Sequence for Rosetta Code

 

Acc = array:set(1, 1, Tmp),

hofstadter(?MAX, 2, Acc, 0).

{{out}}

<pre>

=={{header|ERRE}}==

{{output|ERRE}}

PROGRAM HOFSTADER_Q

 

PRINT("Number of Q(n)<Q(n+1) for n<=10000 : ";NN)

END PROGRAM

Note: The extra credit was limited to 10000 because memory addressable range is limited to 64K.

If you want to implement extra credit for 100,000 you must use external file for array Q%[].

 

 

 

{{out}}

 

=={{header|Factor}}==

We define a method next that takes a sequence of the first n Q values and appends the next one to it. Then we perform it 1000 times on <code>{ 1 1 }</code> and show the first 10 and 999th (because the list is zero-indexed) elements.

dup 2 tail* over length [ swap - ] curry map

[ dupd swap nth ] map 0 [ + ] reduce suffix ;

( scratchpad ) { 1 1 } 1000 [ next ] times dup 10 head . 999 swap nth .

{ 1 1 2 3 3 4 5 5 6 6 }

 

=={{header|Fortran}}==

The latter-day function COUNT(''logical expression'') could easily be replaced by a simple test-and-count in the DO-loop preparing the array. One hopes that the compiler produces sensible code rather than creating an auxiliary array of boolean results then counting the ''true'' values. Rather more clunky is the need to employ odd structure for the input loop so as to handle possible bad input (text, rather than a valid number, for example) and who knows, end-of-file might happen also.

 

Calculate the Hofstadter Q-sequence, using a big array rather than recursion.

INTEGER ENUFF

999 WRITE (6,*) "Bye."

END

 

Output:

Bye.

</pre>

 

=={{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))

{{out}}

<pre>

Q(1000000) = 512066

</pre>

 

=={{header|Haskell}}==

The basic task:

 

qq = 0 : 1 : 1 : map g [3..]

g n = qq !! (n - qq !! (n-1)) + qq !! (n - qq !! (n-2))

*Main> (take 10 qSequence, qSequence !! (1000-1))

([1,1,2,3,3,4,5,5,6,6],502)

 

Extra credit task:

 

 

qSequence n = arr

. _S (zipWith (-)) tail . take n . elems $ arr )

 

 

{{out}}

([1,1,2,3,3,4,5,5,6,6],502,49798)

(0.09 secs, 18879708 bytes)

Prelude Main> qSeqTest 1000000 100000 -- 1,000,000-th item

([1,1,2,3,3,4,5,5,6,6],512066,49798)

 

Using a list (more or less) seemlessly backed up by a double resizing array:

main = do

{{out}}

<pre>

 

List backed up by a list of arrays, with nominal constant lookup time. ''Somehow'' faster than the previous method.

import Data.Int (Int64)

q = qq [listArray (1,2) [1,1]] 1 where

-- Only a perf test. Task can be done exactly the same as above

main = print $ sum qqq

 

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

 

procedure main()

runerr(500,n)

}

 

{{libheader|Icon Programming Library}}

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

 

 

=={{header|J}}==

Q=: verb define

n=. >./,y

end.

y{Qs

 

 

1 1 2 3 3 4 5 5 6 6

Q 1000

502

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

 

'''Note''': The bottom-up solution uses iteration and doesn't risk failure due to recursion limits or cache overflows. The top-down solution uses recursion, and likely hews closer to the spirit of the task. While this latter uses memoization/caching, at some point it will still hit a recursion limit (depends on the environment; in mine, it barfs at N=4402). We use the bottom up version for the extra credit part of this task (the expression which compares adjacent numbers and gave us the result 49798).

[[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");

}

{{out}}

<pre>Q(1) = 1

 

=={{header|JavaScript}}==

Based on memoization example from 'JavaScript: The Good Parts'.

var memo = [1,1,1];

var Q = function (n) {

 

console.log('Q(1000) = ' + hofstadterQ(1000));

{{out}}

<pre>

Q(10) = 6

Q(1000) = 502</pre>

 

=={{header|jq}}==

formula also holds for n == 2, and so that we can cache Q(n) at the

n-th position of an array with index origin 0.

# For n>=2, Q(n) = Q(n - Q(n-1)) + Q(n - Q(n-2))

def Q:

((range(0;11), 1000) | "Q(\(.)) = \( . | Q)"),

 

===Transcript===

$ uname -a

Darwin Mac-mini 13.3.0 Darwin Kernel Version 13.3.0: Tue Jun 3 21:27:35 PDT 2014; root:xnu-2422.110.17~1/RELEASE_X86_64 x86_64

real 0m0.562s

user 0m0.541s

 

=={{header|Julia}}==

The following implementation accepts an argument that is a single integer, an array of integers, or a range:

 

{{out}}

 

And we can also count the number of times a value is less than its predecessor by, for example:

Since the implementation is non-recursive, there is no issue with recursion limits.

 

=={{header|Maple}}==

We use automatic memoisation ("option remember") in the following. The use of "option system" assures that memoised values can be garbage collected.

option remember, system;

if n = 1 or n = 2 then

thisproc( n - thisproc( n - 1 ) ) + thisproc( n - thisproc( n - 2 ) )

end if

From this we get:

1, 1, 2, 3, 3, 4, 5, 5, 6, 6

 

> Q( 1000 );

To determine the number of "flips", we proceed as follows.

> for i from 2 to 100000 do

> if L[ i ] < L[ i - 1 ] then

> end do:

> flips;

Alternatively, we can build the sequence in an array.

local a := Array( 1 .. n );

a[ 1 ] := 1;

end do;

flips

This gives the same result.

 

=={{header|Mathematica}} / {{header|Wolfram Language}}==

Hofstadter[n_Integer?Positive] := Hofstadter[n] = Block[{$RecursionLimit = Infinity},

Hofstadter[n - Hofstadter[n - 1]] + Hofstadter[n - Hofstadter[n - 2]]

{{out}}

{1,1,2,3,3,4,5,5,6,6}

Hofstadter[1000]

502

Count[Differences[Hofstadter /@ Range[100000]], _?Negative]

 

=={{header|MATLAB}} / {{header|Octave}}==

This solution pre-allocates memory and is an iterative solution, so caching or recursion limits do not apply.

%% zeros are used to pre-allocate memory, this is not strictly necessary but can significantly improve performance for large N

Q = [1,1,zeros(1,N-2)];

Q(n) = Q(n-Q(n-1))+Q(n-Q(n-2));

end;

Confirm and display that the first ten terms of the sequence are: 1, 1, 2, 3, 3, 4, 5, 5, 6, and 6

<pre>>> Qsequence(10)

ans = 49798

</pre>

 

=={{header|Nim}}==

 

echo q[0..9]

 

var lessCount = 0

if q[n] < q[n-1]:

inc lessCount

{{out}}

<pre>@[1, 1, 2, 3, 3, 4, 5, 5, 6, 6]

=={{header|Oberon-2}}==

Works with oo2c version 2

MODULE Hofstadter;

IMPORT

Out.String("terms less than the previous: ");Out.LongInt(count,4);Out.Ln

END Hofstadter.

Output:

<pre>

</pre>

 

 

| q i |

ListBuffer newSize(100000) dup add(1) dup add(1) ->q

0 3 100000 for: i [

]

 

{{out}}

=={{header|PARI/GP}}==

Straightforward, unoptimized version; about 1 ms.

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)"));

 

{{out}}

 

=={{header|Pascal}}==

 

const

inc(flips);

writeln('Flips: ', flips);

{{out}}

<pre>:> ./HofstadterQSequence

=={{header|Perl}}==

 

push @Q, $Q[-$Q[-1]] + $Q[-$Q[-2]] for 1..100_000;

say "First 10 terms: [@Q[1..10]]";

say "Term 1000: $Q[1000]";

{{out}}

<pre>First 10 terms: [1 1 2 3 3 4 5 5 6 6]

 

A more verbose and less idiomatic solution:

use warnings;

use strict;

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

"than their preceding terms!\n";

{{out}}

<pre>1

I could have chosen to do recursion instead of iteration, as perl has no limit on how deeply one may recurse, but did not see the benefit of doing so.

 

use strict;

use warnings;

}

print "Extra credit: $count\n";

{{out}}

<pre>

</pre>

 

 

 

 

{{out}}

 

=={{header|PicoLisp}}==

(cache '(NIL) N

(if (>= 2 N)

(+

(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|PL/I}}==

/* Hofstrader Q sequence for any "n". */

 

end;

end H;

{{out}}

<pre>

</pre>

Bonus to produce the count of unordered values:

declare tally fixed binary (31) initial (0);

 

end;

put skip data (tally);

{{out}}

<pre>

TALLY= 49798;

</pre>

 

=={{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." %

 

{{out|Combined output}}

 

===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|Racket}}==

#lang racket

 

;; extra credit

(for/sum ([i 100000]) (if (< (Q (add1 i)) (Q i)) 1 0))

 

{{out}}

49798

</pre>

 

=={{header|REXX}}==

===non-recursive===

The REXX language doesn't allow expressions for stemmed array indices, so a temporary variable must be used.

 

<pre>

 

 

 

</pre>

 

This REXX example is identical to the first version

except that it uses a function to retrieve array elements which may have index expressions.

 

 

Because of the additional subroutine (function) invokes, this REXX version is about half as fast as the 1^st REXX version.

 

===recursive===

 

 

=={{header|Ruby}}==

def Q(n)

if @cache[n].nil?

prev = q

end

{{out}}

<pre>first 10 numbers in the sequence: [1, 1, 2, 3, 3, 4, 5, 5, 6, 6]

 

=={{header|Run BASIC}}==

dim Q(n)

Q(1) = 1

if i > 20 then print "n=";using("####",i);using("####",Q(i))

end

{{out}}

<pre>

Rust doesn't allow static Vec's (but there's lazy_static crate), thus memoization storage is allocated in <code>main</code>.

 

let cur_len=q.len()-1;

let i=x as usize;

println!("Term is less than preceding term {} times", nless);

}

{{out}}

<pre>

Naive but elegant version using only recursion doesn't work

because runtime is excessive increasing ...

val Q: Int => Int = n => {

if (n <= 2) 1

(1 to 10).map(i=>(i,Q(i))).foreach(t=>println("Q("+t._1+") = "+t._2))

println("Q("+1000+") = "+Q(1000))

 

 

Thus we are forced to use a caching featured version.

 

 

val HofQ = scala.collection.mutable.Map((1->1),(2->1))

println("Q("+1000+") = "+Q(1000))

println((3 to 100000).filter(i=>Q(i)<Q(i-1)).size)

{{out}}

<pre>Q(1) = 1

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.

(define filled 3)

(define len 3)

(if (>= i 100000) s

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

{{out}}

<pre>Q(1 .. 10): 1 1 2 3 3 4 5 5 6 6

 

=={{header|Seed7}}==

 

const type: intHash is hash [integer] integer;

end for;

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

 

{{out}}

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

</pre>

 

=={{header|Sidef}}==

Using a memoized function:

}

say "Term 1000: #{Q(1000)}"

 

Using an array:

100_000.times {

Q << (Q[-Q[-1]] + Q[-Q[-2]])

}

 

say "Term 1000: #{Q[1000]}"

{{out}}

<pre>

Term 1000: 502

Terms less than preceding in first 100k: 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)}]]}]

}

{{out}}

<pre>

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

</pre>

 

=={{header|VBScript}}==

Sub q_sequence(n)

Dim Q()

 

q_sequence(100000)

 

{{Out}}

Number of times the member of the sequence is less than its preceding term: 49798

</pre>

 

=={{header|Visual FoxPro}}==

LOCAL p As Integer, i As Integer

CLEAR

RETURN aq[n]

ENDFUNC

{{out}}

<pre>

100000th term: 48157

Number of terms less than the preceding term: 49798

</pre>

 

=={{header|XPL0}}==

int N, C, Q(100_001);

[Q(1):= 1; Q(2):= 1; C:= 0;

IntOut(0, Q(1000)); CrLf(0);

IntOut(0, C); CrLf(0);

 

{{out}}

49798

</pre>

 

=={{header|zkl}}==

{{trans|ALGOL 68}}

q:=(n+1).pump(List.createLong(n+1).write); // (0,1,2,...,n) base 1

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

flip := 0;

foreach i in (n){ flip += (q[i] > q[i + 1]) }

{{out}}

<pre>

flips: 49798

</pre>