Rosetta Code

Hofstadter Q sequence: Difference between revisions

Page Discussion

Hofstadter Q sequence (view source)

Revision as of 20:36, 9 December 2023

18,705 bytes added ,  5 months ago
m
→‎{{header|Wren}}: Changed to Wren S/H
(Added Quackery.)
m (→‎{{header|Wren}}: Changed to Wren S/H)
 
(25 intermediate revisions by 17 users not shown)
Line 24:
{{trans|C}}
 
<langsyntaxhighlight lang="11l">V qseq = [0] * 100001
qseq[1] = 1
qseq[2] = 1
Line 38:
I qseq[i] < qseq[i-1]
less_than_preceding++
print(‘Times a member of the sequence is less than its preceding term: ’less_than_preceding)</langsyntaxhighlight>
 
{{out}}
Line 49:
=={{header|360 Assembly}}==
{{trans|PL/I}}
<langsyntaxhighlight lang="360asm">* Hofstrader q sequence for any n - 18/10/2015
HOFSTRAD CSECT
USING HOFSTRAD,R15 set base register
Line 99:
Q DS 1000F array q(1000)
YREGS
END HOFSTRAD</langsyntaxhighlight>
{{out}}
<pre style="height:16ex">
Line 117:
=={{header|8080 Assembly}}==
 
<langsyntaxhighlight lang="8080asm">puts: equ 9 ; CP/M call to print a string
org 100h
;;; Generate the first 1000 members of the Q sequence
Line 238:
db '*****' ; Placeholder for number
num: db ' $'
qq: dw 1,1 ; Q sequence stored here, starting with 1, 1</langsyntaxhighlight>
 
{{out}}
Line 247:
=={{header|8086 Assembly}}==
 
<langsyntaxhighlight lang="asm">puts: equ 9 ; MS-DOS syscall to print a string
cpu 8086
org 100h
Line 307:
num: db ' $'
Q: dw 1,1
</syntaxhighlight>
</lang>
 
{{out}}
Line 313:
<pre>First 10 terms are: 1 1 2 3 3 4 5 5 6 6
1000th term is: 502</pre>
 
=={{header|Action!}}==
<syntaxhighlight lang="action!">PROC Main()
DEFINE MAX="1000"
INT ARRAY q(MAX+1)
INT i
 
q(1)=1 q(2)=1
FOR i=3 TO MAX
DO
q(i)=q(i-q(i-1))+q(i-q(i-2))
OD
 
FOR i=1 TO 10
DO
PrintF("%I: %I%E",i,q(i))
OD
PrintF("%I: %I%E",MAX,q(MAX))
RETURN</syntaxhighlight>
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Hofstadter_Q_sequence.png Screenshot from Atari 8-bit computer]
<pre>
1: 1
2: 1
3: 2
4: 3
5: 3
6: 4
7: 5
8: 5
9: 6
10: 6
1000: 502
</pre>
 
=={{header|Ada}}==
<langsyntaxhighlight Adalang="ada">with Ada.Text_IO;
 
procedure Hofstadter_Q_Sequence is
Line 373 ⟶ 407:
-- 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;</langsyntaxhighlight>
 
{{out}}
Line 386 ⟶ 420:
{{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''.}}
 
'''File: Hofstadter_Q_sequence.a68'''<langsyntaxhighlight lang="algol68">#!/usr/local/bin/a68g --script #
 
INT n = 100000;
Line 409 ⟶ 443:
 
printf(($"flips: "g(0)l$, flip))
)</langsyntaxhighlight>
{{out}}
<pre>
Line 418 ⟶ 452:
 
=={{header|ALGOL-M}}==
<langsyntaxhighlight lang="algolm">begin
integer array Q[1:1000];
integer n;
Line 431 ⟶ 465:
 
write("The 1000th term is:", Q[1000]);
end</langsyntaxhighlight>
{{out}}
<pre>The first 10 terms are:
1 1 2 3 3 4 5 5 6 6
The 1000th term is: 502</pre>
 
=={{header|ALGOL W}}==
<syntaxhighlight lang="algolw">begin % find elements of the Hofstader Q sequence Q(1) = Q(2) = 1 %
% Q(n) = Q( n - Q( n - 1 ) ) + Q( n - Q( n - 2 ) ) for n > 2 %
integer MAX_Q;
max_Q := 100000;
begin
integer array Q ( 1 :: MAX_Q );
integer array xQ ( 1 :: 10 );
integer ltCount;
logical valuesOk;
% expected values of the first 10 elements %
xQ( 1 ) := xQ( 2 ) := 1;
xQ( 3 ) := 2; xQ( 4 ) := xQ( 5 ) := 3; xQ( 6 ) := 4;
xQ( 7 ) := xQ( 8 ) := 5; xQ( 9 ) := xQ( 10 ) := 6;
% calculate the sequence and count how often Q( n ) < Q( n - 1 ) %
ltCount := 0;
Q( 1 ) := Q( 2 ) := 1;
for n := 3 until MAX_Q do begin
Q( n ) := Q( n - Q( n - 1 ) ) + Q( n - Q( n - 2 ) );
if Q( n ) < Q( n - 1 ) then ltCount := ltCount + 1
end for_n ;
valuesOk := true;
write( "The first 10 terms of the Hofstader Q sequence:" );
for i := 1 until 10 do begin
writeon( i_w := 1, s_w := 0, " ", Q( i ) );
if Q( i ) not = xQ( i ) then begin
writeon( i_w := 1, s_w := 0, "-EXPECTED-", xQ( i ) );
valuesOk := false
end if_Q_i_ne_xQ_i
end for_i ;
write( i_w := 1, s_w := 0, "The 1000th term is: ", Q( 1000 ) );
if Q( 1000 ) not = 502 then begin
writeon( "-EXPECTED-502" );
valuesOk := false
end if_Q_100_ne_502 ;
if valuesOk then write( " (Computed values are as expected)" )
else write( "Values NOT as expected" );
write( i_w := 1, s_w := 0, "Q(n) < Q(n-1) ", ltCount," times for n up to ", MAX_Q )
end
end.</syntaxhighlight>
{{out}}
<pre>
The first 10 terms of the Hofstader Q sequence: 1 1 2 3 3 4 5 5 6 6
The 1000th term is: 502
(Computed values are as expected)
Q(n) < Q(n-1) 49798 times for n up to 100000
</pre>
 
=={{header|APL}}==
 
<langsyntaxhighlight APLlang="apl">∇ Q_sequence;seq;size
size←100000
seq←{⍵,+/⍵[(1+⍴⍵)-¯2↑⍵]}⍣(size-2)⊢1 1
Line 446 ⟶ 528:
⎕←'The 1000th term is:', seq[1000]
⎕←(+/ 2>/seq),'terms were preceded by a larger term.'
∇</langsyntaxhighlight>
 
{{out}}
Line 457 ⟶ 539:
 
=={{header|ARM Assembly}}==
<syntaxhighlight lang="text">.text
.global _start
_start: ldr r6,=qs @ R6 = base register for Q array
Line 570 ⟶ 652:
.align 4
.space 8 @ Buffer for number output
qs: .space 4 * 100001 @ One word per term</langsyntaxhighlight>
 
{{out}}
Line 580 ⟶ 662:
=={{header|Arturo}}==
 
<langsyntaxhighlight lang="rebol">q: new [1 1]
n: 2
while [n<1001][
Line 588 ⟶ 670:
 
print ["First ten items:" first.n: 10 q]
print ["1000th item:" q\[999]]</langsyntaxhighlight>
 
{{out}}
Line 596 ⟶ 678:
 
=={{header|AutoHotkey}}==
<langsyntaxhighlight AutoHotkeylang="autohotkey">SetBatchLines, -1
Q := HofsQSeq(100000)
 
Line 615 ⟶ 697:
}
return Q
}</langsyntaxhighlight>
{{out}}
<pre>First ten: 1, 1, 2, 3, 3, 4, 5, 5, 6, 6,
Line 622 ⟶ 704:
 
=={{header|AWK}}==
<langsyntaxhighlight lang="awk">#!/usr/bin/awk -f
BEGIN {
N = 100000
Line 643 ⟶ 725:
}
return seq
} </langsyntaxhighlight>
 
<pre>Q-sequence(1..10) : 1 1 2 3 3 4 5 5 6 6
Line 649 ⟶ 731:
number of Q(n)<Q(n+1) for n<=100000 : 49798</pre>
 
=={{header|BASIC256BASIC}}==
==={{header|BASIC256}}===
{{trans|FreeBASIC}}
<syntaxhighlight lang="basic256">
<lang BASIC256>
limite = 100000
dim Q[limite+1]
Line 669 ⟶ 752:
print "Término número 1000: "; Q[1000]
print "Términos menores que los anteriores: "; cont
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 675 ⟶ 758:
</pre>
 
==={{header|BBC BASIC}}===
<langsyntaxhighlight lang="bbcbasic"> PRINT "First 10 terms of Q = " ;
FOR i% = 1 TO 10 : PRINT ;FNq(i%, c%) " "; : NEXT : PRINT
PRINT "1000th term = " ; FNq(1000, c%)
Line 693 ⟶ 776:
IF q%(i%) < q%(i%-1) THEN c% += 1
NEXT
= q%(n%)</langsyntaxhighlight>
{{out}}
<pre>
Line 701 ⟶ 784:
Term is less than preceding term 49798 times
</pre>
 
==={{header|QBasic}}===
{{works with|QBasic|1.1}}
{{works with|QuickBasic|4.5}}
<syntaxhighlight lang="qbasic">CONST limite = 10000
DIM Q(limite)
Q(1) = 1
Q(2) = 1
 
cont = 0
FOR i = 3 TO limite
Q(i) = Q(i - Q(i - 1)) + Q(i - Q(i - 2))
IF Q(i) < Q(i-1) THEN cont = cont + 1
NEXT i
 
PRINT "First 10 terms: ";
FOR i = 1 TO 10
PRINT Q(i); " ";
NEXT i
 
PRINT
PRINT "Term 1000: "; Q(1000)
PRINT "Terms less than preceding in first 100k: "; cont</syntaxhighlight>
 
==={{header|True BASIC}}===
<syntaxhighlight lang="qbasic">LET limite = 100000
 
DIM q(0)
MAT REDIM q(limite)
LET q(1) = 1
LET q(2) = 1
 
LET count = 0
FOR i = 3 TO limite
LET q(i) = q(i-q(i-1))+q(i-q(i-2))
IF q(i) < q(i-1) THEN
LET count = count + 1
END IF
NEXT i
 
PRINT "First 10 terms: ";
FOR i = 1 TO 10
PRINT q(i);
NEXT i
 
PRINT
PRINT "Term 1000: "; q(1000)
PRINT "Terms less than preceding in first 100k: "; count
END</syntaxhighlight>
{{out}}
<pre>Same as FreeBASIC entry.</pre>
 
==={{header|XBasic}}===
{{works with|Windows XBasic}}
<syntaxhighlight lang="qbasic">PROGRAM "Hofstadter Q sequence"
VERSION "0.0000"
 
DECLARE FUNCTION Entry ()
 
FUNCTION Entry ()
limite = 1e5
DIM q[limite]
q[1] = 1
q[2] = 1
count = 0
FOR i = 3 TO limite
q[i] = q[i-q[i-1]] + q[i-q[i-2]]
IF q[i] < q[i-1] THEN
INC count
END IF
NEXT i
PRINT "First 10 terms: ";
FOR i = 1 TO 10
PRINT q[i];
NEXT i
PRINT "\nTerm 1000: "; q[1000]
PRINT "Terms less than preceding in first 100k: "; count
END FUNCTION
END PROGRAM
</syntaxhighlight>
{{out}}
<pre>Same as FreeBASIC entry.</pre>
 
==={{header|Yabasic}}===
<syntaxhighlight lang="basic">limite = 1e5
dim q(limite)
q(1) = 1
q(2) = 1
 
count = 0
for i = 3 to limite
q(i) = q(i-q(i-1)) + q(i-q(i-2))
if q(i) < q(i-1) count = count + 1
next i
 
print "First 10 terms: ";
 
for i = 1 to 10
print q(i), " ";
next i
 
print "\nTerm 1000: ", q(1000)
print "Terms less than preceding in first 100k: ", count
end</syntaxhighlight>
{{out}}
<pre>Same as FreeBASIC entry.</pre>
 
=={{header|Bracmat}}==
<langsyntaxhighlight lang="bracmat">( 0:?memocells
& tbl$(memo,!memocells+1) { allocate array }
& ( Q
Line 734 ⟶ 926:
)
& out$!lessThan
);</langsyntaxhighlight>
Output:
<pre>1 1 2 3 3 4 5 5 6 6
Line 741 ⟶ 933:
 
=={{header|BCPL}}==
<langsyntaxhighlight BCPLlang="bcpl">get "libhdr"
 
let start() be
Line 755 ⟶ 947:
writef("*NThe 1000th term is: %N*N", Q!1000)
$)</langsyntaxhighlight>
{{out}}
<pre>The first 10 terms are: 1 1 2 3 3 4 5 5 6 6
Line 761 ⟶ 953:
 
=={{header|C}}==
<langsyntaxhighlight lang="c">#include <stdio.h>
#include <stdlib.h>
 
Line 784 ⟶ 976:
printf("flips: %d\n", flip);
return 0;
}</langsyntaxhighlight>
{{out}}
<pre>1 1 2 3 3 4 5 5 6 6
Line 793 ⟶ 985:
=={{header|C sharp}}==
 
<langsyntaxhighlight Clang="c sharp">using System;
using System.Collections.Generic;
 
Line 856 ⟶ 1,048:
}
}
}</langsyntaxhighlight>
 
{{out}}
Line 875 ⟶ 1,067:
solution modeled after Perl solution
 
<langsyntaxhighlight Cpplang="cpp">#include <iostream>
int main() {
Line 894 ⟶ 1,086:
std::cout << less_than_preceding << " times a number was preceded by a greater number!" << std::endl;
return 0;
}</langsyntaxhighlight>
{{out}}
<pre>The first 10 numbers are: 1 1 2 3 3 4 5 5 6 6
Line 904 ⟶ 1,096:
The subsequences are vectors for efficient indexing.
''qfirst'' iterates ''qs'' so the nth iteration is Q{1..n].
<langsyntaxhighlight lang="clojure">(defn qs [q]
(let [n (count q)]
(condp = n
Line 916 ⟶ 1,108:
(println "first 10:" (qfirst 10))
(println "1000th:" (last (qfirst 1000)))
(println "extra credit:" (->> (qfirst 100000) (partition 2 1) (filter #(apply > %)) count))</langsyntaxhighlight>
{{out}}
<syntaxhighlight lang="text">first 10: [1 1 2 3 3 4 5 5 6 6]
1000th: 502
extra credit: 49798</langsyntaxhighlight>
 
=={{header|CLU}}==
<syntaxhighlight lang="clu">q_seq = proc (n: int) returns (sequence[int])
q: array[int] := array[int]$[1,1]
for i: int in int$from_to(3,n) do
array[int]$addh(q, q[i-q[i-1]] + q[i-q[i-2]])
end
return(sequence[int]$a2s(q))
end q_seq
 
start_up = proc ()
po: stream := stream$primary_output()
q: sequence[int] := q_seq(100000)
stream$puts(po, "First 10 terms:")
for i: int in int$from_to(1,10) do
stream$puts(po, " " || int$unparse(q[i]))
end
stream$puts(po, "\n1000th term: " || int$unparse(q[1000]))
flips: int := 0
for i: int in int$from_to(2, sequence[int]$size(q)) do
if q[i-1]>q[i] then flips := flips + 1 end
end
stream$putl(po, "\nflips: " || int$unparse(flips))
end start_up</syntaxhighlight>
{{out}}
<pre>First 10 terms: 1 1 2 3 3 4 5 5 6 6
1000th term: 502
flips: 49798</pre>
 
=={{header|CoffeeScript}}==
{{trans|JavaScript}}
<langsyntaxhighlight lang="coffeescript">hofstadterQ = do ->
memo = [ 1 ,1, 1]
Q = (n) ->
Line 934 ⟶ 1,158:
# some results:
console.log 'Q(' + i + ') = ' + hofstadterQ(i) for i in [1..10]
console.log 'Q(1000) = ' + hofstadterQ(1000)</langsyntaxhighlight>
{{out}}
<pre>Q(1) = 1
Line 946 ⟶ 1,170:
Q(9) = 6
Q(10) = 6
Q(1000) = 502</pre>
 
=={{header|COBOL}}==
<syntaxhighlight lang="cobol"> IDENTIFICATION DIVISION.
PROGRAM-ID. Q-SEQ.
DATA DIVISION.
WORKING-STORAGE SECTION.
01 SEQ.
02 Q PIC 9(3) OCCURS 1000 TIMES.
02 Q-TMP1 PIC 9(3).
02 Q-TMP2 PIC 9(3).
02 N PIC 9(4).
01 DISPLAYING.
02 ITEM PIC Z(3).
02 IX PIC Z(4).
PROCEDURE DIVISION.
MAIN-PROGRAM.
PERFORM GENERATE-SEQUENCE.
PERFORM SHOW-ITEM
VARYING N FROM 1 BY 1
UNTIL N IS GREATER THAN 10.
SET N TO 1000.
PERFORM SHOW-ITEM.
STOP RUN.
GENERATE-SEQUENCE.
SET Q(1) TO 1.
SET Q(2) TO 1.
PERFORM GENERATE-ITEM
VARYING N FROM 3 BY 1
UNTIL N IS GREATER THAN 1000.
GENERATE-ITEM.
COMPUTE Q-TMP1 = N - Q(N - 1).
COMPUTE Q-TMP2 = N - Q(N - 2).
COMPUTE Q(N) = Q(Q-TMP1) + Q(Q-TMP2).
SHOW-ITEM.
MOVE N TO IX.
MOVE Q(N) TO ITEM.
DISPLAY 'Q(' IX ') = ' ITEM.</syntaxhighlight>
{{out}}
<pre>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</pre>
 
=={{header|Common Lisp}}==
<langsyntaxhighlight lang="lisp">(defparameter *mm* (make-hash-table :test #'equal))
 
;;; generic memoization macro
Line 975 ⟶ 1,253:
(if (< next-q last-q) (incf c))
(setf last-q next-q))
finally (return c)))</langsyntaxhighlight>
{{out}}
<pre>First of Q: (1 1 2 3 3 4 5 5 6 6)
Line 981 ⟶ 1,259:
Bumps up to 100000: 49798</pre>
 
Although the above definition of <code>q</code> is more general, for this specific problem the following is faster:<langsyntaxhighlight lang="lisp">(let ((cc (make-array 3 :element-type 'integer
:initial-element 1
:adjustable t
Line 992 ⟶ 1,270:
(aref cc (- n (aref cc (- n 2)))))
cc))
(aref cc n)))</langsyntaxhighlight>
 
=={{header|Cowgol}}==
<langsyntaxhighlight lang="cowgol">include "cowgol.coh";
 
# Generate 1000 terms of the Q sequence
Line 1,021 ⟶ 1,299:
print("The 1000th term is: ");
print_i16(Q[1000]);
print_nl();</langsyntaxhighlight>
 
{{out}}
Line 1,029 ⟶ 1,307:
 
=={{header|D}}==
<langsyntaxhighlight lang="d">import std.stdio, std.algorithm, std.functional, std.range;
 
int Q(in int n) nothrow
Line 1,048 ⟶ 1,326:
iota(2, 100_001).count!(i => Q(i) < Q(i - 1)));
}
</syntaxhighlight>
</lang>
{{out}}
<pre>Q(n) for n = [1..10] is: [1, 1, 2, 3, 3, 4, 5, 5, 6, 6]
Line 1,058 ⟶ 1,336:
{{trans|Python}}
Same output.
<langsyntaxhighlight lang="d">import std.stdio, std.algorithm, std.range, std.array;
 
uint Q(in int n) nothrow
Line 1,077 ⟶ 1,355:
iota(2, 100_001).count!(i => Q(i) < Q(i - 1)));
}
</syntaxhighlight>
</lang>
 
===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.
 
<syntaxhighlight lang="d">
<lang d>
import std.stdio;
 
Line 1,114 ⟶ 1,392:
writefln("Q(i) is less than Q(i-1) for i [2..100_000] %d times.", lt);
}
</syntaxhighlight>
</lang>
 
=={{header|Dart}}==
Naive version using only recursion (Q(1000) fails due to browser script runtime restrictions)
<langsyntaxhighlight lang="dart">int Q(int n) => n>2 ? Q(n-Q(n-1))+Q(n-Q(n-2)) : 1;
 
main() {
Line 1,125 ⟶ 1,403:
}
print("Q(1000)=${Q(1000)}");
}</langsyntaxhighlight>
 
Version featuring caching.
<langsyntaxhighlight lang="dart">class Q {
Map<int,int> _table;
 
Line 1,169 ⟶ 1,447:
}
print("value is smaller than previous $count times");
}</langsyntaxhighlight>
{{out}}
<pre>Q(1)=1
Line 1,185 ⟶ 1,463:
 
If the maximum number is known, filling an array is probably the fastest solution.
<langsyntaxhighlight lang="dart">main() {
List<int> q=new List<int>(100001);
q[1]=q[2]=1;
Line 1,201 ⟶ 1,479:
print("Q(1000)=${q[1000]}");
print("value is smaller than previous $count times");
}</langsyntaxhighlight>
 
=={{header|Draco}}==
<syntaxhighlight lang="draco">proc nonrec make_Q([*] word q) void:
word n;
q[1] := 1;
q[2] := 1;
for n from 3 upto dim(q,1)-1 do
q[n] := q[n-q[n-1]] + q[n-q[n-2]]
od
corp
 
proc nonrec main() void:
word MAX = 1000;
word i;
[MAX+1] word q;
make_Q(q);
write("The first 10 terms are:");
for i from 1 upto 10 do write(" ", q[i]) od;
writeln();
writeln("The 1000th term is: ", q[1000])
corp</syntaxhighlight>
{{out}}
<pre>The first 10 terms are: 1 1 2 3 3 4 5 5 6 6
The 1000th term is: 502</pre>
 
=={{header|EasyLang}}==
{{trans|Lua}}
<syntaxhighlight>
proc hofstadter limit . q[] .
q[] = [ 1 1 ]
for n = 3 to limit
q[] &= q[n - q[n - 1]] + q[n - q[n - 2]]
.
.
proc count . q[] cnt .
for i = 2 to len q[]
if q[i] < q[i - 1]
cnt += 1
.
.
.
hofstadter 100000 hofq[]
for i = 1 to 10
write hofq[i] & " "
.
print ""
print hofq[1000]
count hofq[] cnt
print cnt
</syntaxhighlight>
 
=={{header|EchoLisp}}==
<langsyntaxhighlight lang="scheme">
(define RECURSE_BUMP 500) ;; minimum of chrome:500 safari:1000 firefox:2000
 
Line 1,228 ⟶ 1,557:
(Q 1000) → 502
(flips 100000) → 49798
</syntaxhighlight>
</lang>
 
=={{header|Eiffel}}==
<syntaxhighlight lang="eiffel">
<lang Eiffel>
class
APPLICATION
Line 1,293 ⟶ 1,622:
end
 
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 1,307 ⟶ 1,636:
{{trans|Erlang}}
changed collection (Erlang array => Map)
<langsyntaxhighlight lang="elixir">defmodule Hofstadter do
defp flip(v2, v1) when v1 > v2, do: 1
defp flip(_v2, _v1), do: 0
Line 1,330 ⟶ 1,659:
end
 
Hofstadter.main</langsyntaxhighlight>
 
{{out}}
Line 1,340 ⟶ 1,669:
 
=={{header|Erlang}}==
<langsyntaxhighlight lang="erlang">%% @author Jan Willem Luiten <jwl@secondmove.com>
%% Hofstadter Q Sequence for Rosetta Code
 
Line 1,370 ⟶ 1,699:
Acc = array:set(1, 1, Tmp),
hofstadter(?MAX, 2, Acc, 0).
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 1,380 ⟶ 1,709:
=={{header|ERRE}}==
{{output|ERRE}}
<syntaxhighlight lang="erre">
<lang ERRE>
PROGRAM HOFSTADER_Q
 
Line 1,416 ⟶ 1,745:
PRINT("Number of Q(n)<Q(n+1) for n<=10000 : ";NN)
END PROGRAM
</syntaxhighlight>
</lang>
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%[].
 
=={{header|Delphi}}==
{{works with|Delphi|6.0}}
{{libheader|SysUtils,StdCtrls}}
 
 
<syntaxhighlight lang="Delphi">
type TIntArray = array of integer;
 
procedure FillHofstadterArray(var HA: TIntArray);
{Fill array with Hofstader numbers}
{Preset array size to the number of terms you want}
var I: integer;
begin
{Starting condition}
HA[1]:=1; HA[2]:=1;
{Fill array up to last item}
for I:=3 to High(HA) do HA[I]:=HA[I-HA[I-1]]+HA[I-HA[I-2]];
end;
 
 
procedure ShowHofstadterNumbers(Memo: TMemo);
{Fill array with a }
var I, LessCount: integer;
var QArray: TIntArray;
begin
{Select the number of items we want}
SetLength(QArray,100000);
{Fill array}
FillHofstadterArray(QArray);
{Display first 10}
for I:=1 to 10 do Memo.Lines.Add(Format('%4d: %4d',[I,QArray[I]]));
Memo.Lines.Add(Format('%4d: %4d',[1000,QArray[1000]]));
{Count number the number of times Q(n)<Q(n-1)}
LessCount:=0;
for I:=1 to High(QArray) do
if QArray[I]>QArray[I-1] then Inc(LessCount);
Memo.Lines.Add('Count of Q(n)<Q(n-1) = '+IntToStr(LessCount));
end;
 
</syntaxhighlight>
{{out}}
<pre>
1: 1
2: 1
3: 2
4: 3
5: 3
6: 4
7: 5
8: 5
9: 6
10: 6
1000: 502
Count of Q(n)<Q(n-1) = 49997
</pre>
 
 
=={{header|F_Sharp|F#}}==
===The function===
<langsyntaxhighlight lang="fsharp">
// Populate an array with values of Hofstadter Q sequence. Nigel Galloway: August 26th., 2020
let fQ N=let g=Array.length N in N.[0]<-1; N.[1]<-1;(for g in 2..g-1 do N.[g]<-N.[g-N.[g-1]]+N.[g-N.[g-2]])
</syntaxhighlight>
</lang>
===The Tasks===
<langsyntaxhighlight lang="fsharp">
let Q=Array.zeroCreate<int>10 in fQ Q; printfn "%A" Q
let Q=Array.zeroCreate<int>1000 in fQ Q; printfn "%d" (Array.last Q)
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 1,437 ⟶ 1,823:
</pre>
===Extra Credit===
<langsyntaxhighlight lang="fsharp">
let Q=Array.zeroCreate<int>100000 in fQ Q; printfn "%d" (Q|>Seq.pairwise|>Seq.sumBy(fun(n,g)->if n>g then 1 else 0))
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 1,446 ⟶ 1,832:
 
;What is a large number?
<langsyntaxhighlight lang="fsharp">
let Q=Array.zeroCreate<int>2500000000 in fQ Q; printfn "%d" (Array.last Q)
let Q=Array.zeroCreate<int>5000000000 in fQ Q; printfn "%d" (Array.last Q)
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 1,458 ⟶ 1,844:
=={{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.
<langsyntaxhighlight lang="factor">( scratchpad ) : next ( seq -- newseq )
dup 2 tail* over length [ swap - ] curry map
[ dupd swap nth ] map 0 [ + ] reduce suffix ;
Line 1,464 ⟶ 1,850:
( scratchpad ) { 1 1 } 1000 [ next ] times dup 10 head . 999 swap nth .
{ 1 1 2 3 3 4 5 5 6 6 }
502</langsyntaxhighlight>
 
=={{header|Fermat}}==
<syntaxhighlight lang="text">Func Hq(n) = if n<2 then 1 else
Array qq[n+1];
qq[1] := 1;
Line 1,479 ⟶ 1,865:
 
for i=1 to 10 do !Hq(i);!' ' od;
Hq(1000)</langsyntaxhighlight>
{{out}}<pre>
1 1 2 3 3 4 5 5 6 6
Line 1,486 ⟶ 1,872:
=={{header|Forth}}==
{{trans|C}}
<langsyntaxhighlight lang="forth">100000 constant N
 
: q ( n -- addr ) cells here + ;
Line 1,512 ⟶ 1,898:
999 q @ . cr
flips
bye</langsyntaxhighlight>
 
{{out}}
Line 1,524 ⟶ 1,910:
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.
 
<syntaxhighlight lang="fortran">
<lang Fortran>
Calculate the Hofstadter Q-sequence, using a big array rather than recursion.
INTEGER ENUFF
Line 1,555 ⟶ 1,941:
999 WRITE (6,*) "Bye."
END
</syntaxhighlight>
</lang>
 
Output:
Line 1,569 ⟶ 1,955:
 
=={{header|FreeBASIC}}==
<langsyntaxhighlight lang="freebasic">
Const limite = 100000
 
Line 1,591 ⟶ 1,977:
Print "Terminos menores que los anteriores: " &cont
End
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 1,601 ⟶ 1,987:
=={{header|Fōrmulæ}}==
 
In [{{FormulaeEntry|page=https://wiki.formulae.org/?script=examples/Hofstadter_Q_sequence this] page you can see the solution of this task.}}
 
'''Solution'''
Fōrmulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text ([http://wiki.formulae.org/Editing_F%C5%8Drmul%C3%A6_expressions more info]). Moreover, there can be multiple visual representations of the same program. Even though it is possible to have textual representation &mdash;i.e. XML, JSON&mdash; they are intended for transportation effects more than visualization and edition.
 
The following function calculate the given number of terms of the Hofstadter Q sequence:
The option to show Fōrmulæ programs and their results is showing images. Unfortunately images cannot be uploaded in Rosetta Code.
 
[[File:Fōrmulæ - Hofstadter Q sequence 01.png]]
 
'''Case 1''' First 10 terms
 
[[File:Fōrmulæ - Hofstadter Q sequence 02.png]]
 
[[File:Fōrmulæ - Hofstadter Q sequence 03.png]]
 
'''Case 2''' Confirm and display that the 1000th term is 502
 
[[File:Fōrmulæ - Hofstadter Q sequence 04.png]]
 
[[File:Fōrmulæ - Hofstadter Q sequence 05.png]]
 
'''Case 3''' 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,000th term.
 
[[File:Fōrmulæ - Hofstadter Q sequence 06.png]]
 
[[File:Fōrmulæ - Hofstadter Q sequence 07.png]]
 
=={{header|Go}}==
Sure there are ways that run faster or handle larger numbers; for the task though, maps and recursion work just fine.
<langsyntaxhighlight lang="go">package main
 
import "fmt"
Line 1,654 ⟶ 2,060:
func showQ(n int) {
fmt.Printf("Q(%d) = %d\n", n, q(n))
}</langsyntaxhighlight>
{{out}}
<pre>
Line 1,673 ⟶ 2,079:
 
=={{header|GW-BASIC}}==
<langsyntaxhighlight lang="gwbasic">10 DIM Q!(1000)
20 Q(1) = 1: Q(2) = 1
30 FOR N = 3 TO 1000
Line 1,681 ⟶ 2,087:
70 PRINT Q(N)
80 NEXT N
90 PRINT Q(1000)</langsyntaxhighlight>
 
=={{header|Haskell}}==
Line 1,687 ⟶ 2,093:
The basic task:
 
<langsyntaxhighlight Haskelllang="haskell">qSequence = tail qq where
qq = 0 : 1 : 1 : map g [3..]
g n = qq !! (n - qq !! (n-1)) + qq !! (n - qq !! (n-2))
Line 1,694 ⟶ 2,100:
*Main> (take 10 qSequence, qSequence !! (1000-1))
([1,1,2,3,3,4,5,5,6,6],502)
(0.00 secs, 525044 bytes)</langsyntaxhighlight>
 
Extra credit task:
 
<langsyntaxhighlight Haskelllang="haskell">import Data.Array
 
qSequence n = arr
Line 1,718 ⟶ 2,124:
. _S (zipWith (-)) tail . take n . elems $ arr )
 
_S f g x = f x (g x)</langsyntaxhighlight>
 
{{out}}
<langsyntaxhighlight Haskelllang="haskell">Prelude Main> qSeqTest 1000 100000 -- reversals in 100,000
([1,1,2,3,3,4,5,5,6,6],502,49798)
(0.09 secs, 18879708 bytes)
Line 1,727 ⟶ 2,133:
Prelude Main> qSeqTest 1000000 100000 -- 1,000,000-th item
([1,1,2,3,3,4,5,5,6,6],512066,49798)
(2.80 secs, 87559640 bytes)</langsyntaxhighlight>
 
Using a list (more or less) seemlessly backed up by a double resizing array:
<langsyntaxhighlight lang="haskell">q = qq (listArray (1,2) [1,1]) 1 where
qq ar n = (arr!n) : qq arr (n+1) where
l = snd (bounds ar)
Line 1,745 ⟶ 2,151:
putStr("1000-th: "); print (q !! 999)
putStr("flips: ")
print $ length $ filter id $ take 100000 (zipWith (>) q (tail q))</langsyntaxhighlight>
{{out}}
<pre>
Line 1,754 ⟶ 2,160:
 
List backed up by a list of arrays, with nominal constant lookup time. ''Somehow'' faster than the previous method.
<langsyntaxhighlight lang="haskell">import Data.Array
import Data.Int (Int64)
Line 1,774 ⟶ 2,180:
where
qqq :: [Int64]
qqq = map fromIntegral $ take 3000000 q</langsyntaxhighlight>
 
=={{header|Icon}} and {{header|Unicon}}==
<langsyntaxhighlight Iconlang="icon">link printf
 
procedure main()
Line 1,815 ⟶ 2,221:
runerr(500,n)
}
end</langsyntaxhighlight>
 
{{libheader|Icon Programming Library}}
Line 1,834 ⟶ 2,240:
 
=={{header|IS-BASIC}}==
<langsyntaxhighlight ISlang="is-BASICbasic">100 PROGRAM "QSequen.bas"
110 LET LIMIT=1000
120 NUMERIC Q(1 TO LIMIT)
Line 1,845 ⟶ 2,251:
190 PRINT Q(I);
200 NEXT
210 PRINT :PRINT "Term 1000:";Q(1000)</langsyntaxhighlight>
 
=={{header|J}}==
'''Solution''' (''bottom-up''):<langsyntaxhighlight lang="j"> Qs=:0 1 1
Q=: verb define
n=. >./,y
Line 1,855 ⟶ 2,261:
end.
y{Qs
)</langsyntaxhighlight>
 
'''Solution''' (''top-down''):<langsyntaxhighlight lang="j"> Q=: 1:`(+&$:/@:- $:@-& 1 2)@.(>&2)"0 M.</langsyntaxhighlight>
 
'''Example''':<langsyntaxhighlight 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</langsyntaxhighlight>
 
'''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).
Line 1,875 ⟶ 2,281:
[[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.
<langsyntaxhighlight lang="java5">import java.util.HashMap;
import java.util.Map;
 
Line 1,920 ⟶ 2,326:
System.out.println("Q(" + maxN + ") was called the most with " + maxUses + " calls");
}
}</langsyntaxhighlight>
{{out}}
<pre>Q(1) = 1
Line 1,939 ⟶ 2,345:
===ES5===
Based on memoization example from 'JavaScript: The Good Parts'.
<langsyntaxhighlight JavaScriptlang="javascript">var hofstadterQ = function() {
var memo = [1,1,1];
var Q = function (n) {
Line 1,957 ⟶ 2,363:
 
console.log('Q(1000) = ' + hofstadterQ(1000));
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 1,975 ⟶ 2,381:
===ES6===
Memoising with the accumulator of a fold
<langsyntaxhighlight JavaScriptlang="javascript">(() => {
'use strict';
 
Line 2,014 ⟶ 2,420:
.reduce((a, x, i, xs) => x < xs[i - 1] ? a + 1 : a, 0)
};
})();</langsyntaxhighlight>
 
{{Out}}
<langsyntaxhighlight JavaScriptlang="javascript">{"firstTen":[1, 1, 2, 3, 3, 4, 5, 5, 6, 6],
"thousandth":502,
"Q<Q-1UpTo10E5":49798}</langsyntaxhighlight>
 
=={{header|jq}}==
Line 2,027 ⟶ 2,433:
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.
<syntaxhighlight lang="jq">
<lang jq>
# For n>=2, Q(n) = Q(n - Q(n-1)) + Q(n - Q(n-2))
def Q:
Line 2,055 ⟶ 2,461:
((range(0;11), 1000) | "Q(\(.)) = \( . | Q)"),
 
(100000 | "flips(\(.)) = \(flips(.))")</langsyntaxhighlight>
===Transcript===
<langsyntaxhighlight lang="bash">
$ 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
Line 2,077 ⟶ 2,483:
real 0m0.562s
user 0m0.541s
sys 0m0.011s</langsyntaxhighlight>
 
=={{header|Julia}}==
The following implementation accepts an argument that is a single integer, an array of integers, or a range:
<langsyntaxhighlight lang="julia">function hofstQseq(n, typerst::Type=Int)
nmax = maximum(n)
r = Vector{typerst}(nmax)
Line 2,094 ⟶ 2,500:
println("First ten elements of sequence: ", join(hofstQseq(1:10), ", "))
println("1000-th element: ", hofstQseq(1000))
</syntaxhighlight>
</lang>
 
{{out}}
Line 2,101 ⟶ 2,507:
 
And we can also count the number of times a value is less than its predecessor by, for example:
<langsyntaxhighlight lang="julia">seq = hofstQseq(1:100_000)
cnt = count(diff(seq) .< 0)
println("$cnt elements are less than the preceding one.")</langsyntaxhighlight>
 
{{out}}
Line 2,111 ⟶ 2,517:
 
=={{header|Kotlin}}==
<langsyntaxhighlight lang="scala">// version 1.1.4
 
fun main(args: Array<String>) {
Line 2,123 ⟶ 2,529:
val flips = (2..100_000).count { q[it] < q[it - 1] }
println("\nThe number of flips for the first 100,000 terms is : $flips")
}</langsyntaxhighlight>
 
{{out}}
Line 2,134 ⟶ 2,540:
</pre>
 
=={{header|Lua}}==
Here, the whole sequence up to the 100,000th term is generated for the first task, so this is where we risk hitting the recursion limit. As it happens, we do not. The function is called using 'pcall' so that any error would be caught. By increasing the argument on line 19 from 1e5 to 1e8, we can cause LuaJIT to run out of memory, but that is not necessary for this task.
<syntaxhighlight lang="lua">function hofstadter (limit)
local Q = {1, 1}
for n = 3, limit do
Q[n] = Q[n - Q[n - 1]] + Q[n - Q[n - 2]]
end
return Q
end
 
function countDescents (t)
local count = 0
for i = 2, #t do
if t[i] < t[i - 1] then
count = count + 1
end
end
return count
end
 
local noError, hofSeq = pcall(hofstadter, 1e5)
if noError == false then
print("The sequence could not be calculated up to the specified limit.")
os.exit()
end
for i = 1, 10 do
io.write(hofSeq[i] .. " ")
end
print("\n" .. hofSeq[1000])
print(countDescents(hofSeq))</syntaxhighlight>
{{out}}
<pre>1 1 2 3 3 4 5 5 6 6
502
49798</pre>
=={{header|MAD}}==
 
<langsyntaxhighlight MADlang="mad"> NORMAL MODE IS INTEGER
VECTOR VALUES FMT = $2HQ(,I4,3H) =,I4*$
Line 2,149 ⟶ 2,590:
PRINT FORMAT FMT, 1000, Q(1000)
END OF PROGRAM</langsyntaxhighlight>
 
{{out}}
Line 2,169 ⟶ 2,610:
=={{header|Maple}}==
We use automatic memoisation ("option remember") in the following. The use of "option system" assures that memoised values can be garbage collected.
<langsyntaxhighlight Maplelang="maple">Q := proc( n )
option remember, system;
if n = 1 or n = 2 then
Line 2,176 ⟶ 2,617:
thisproc( n - thisproc( n - 1 ) ) + thisproc( n - thisproc( n - 2 ) )
end if
end proc:</langsyntaxhighlight>
From this we get:
<langsyntaxhighlight Maplelang="maple">> seq( Q( i ), i = 1 .. 10 );
1, 1, 2, 3, 3, 4, 5, 5, 6, 6
 
> Q( 1000 );
502</langsyntaxhighlight>
To determine the number of "flips", we proceed as follows.
<langsyntaxhighlight Maplelang="maple">> flips := 0:
> for i from 2 to 100000 do
> if L[ i ] < L[ i - 1 ] then
Line 2,191 ⟶ 2,632:
> end do:
> flips;
49798</langsyntaxhighlight>
Alternatively, we can build the sequence in an array.
<langsyntaxhighlight Maplelang="maple">Qflips := proc( n )
local a := Array( 1 .. n );
a[ 1 ] := 1;
Line 2,207 ⟶ 2,648:
end do;
flips
end proc:</langsyntaxhighlight>
This gives the same result.
<langsyntaxhighlight Maplelang="maple">> Qflips( 10^5 );
49798</langsyntaxhighlight>
 
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<langsyntaxhighlight Mathematicalang="mathematica">Hofstadter[1] = Hofstadter[2] = 1;
Hofstadter[n_Integer?Positive] := Hofstadter[n] = Block[{$RecursionLimit = Infinity},
Hofstadter[n - Hofstadter[n - 1]] + Hofstadter[n - Hofstadter[n - 2]]
]</langsyntaxhighlight>
{{out}}
<langsyntaxhighlight Mathematicalang="mathematica">Hofstadter /@ Range[10]
{1,1,2,3,3,4,5,5,6,6}
Hofstadter[1000]
502
Count[Differences[Hofstadter /@ Range[100000]], _?Negative]
49798</langsyntaxhighlight>
 
=={{header|MATLAB}} / {{header|Octave}}==
This solution pre-allocates memory and is an iterative solution, so caching or recursion limits do not apply.
<langsyntaxhighlight MATLABlang="matlab">function Q = Qsequence(N)
%% 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)];
Line 2,233 ⟶ 2,674:
Q(n) = Q(n-Q(n-1))+Q(n-Q(n-2));
end;
end; </langsyntaxhighlight>
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)
Line 2,247 ⟶ 2,688:
ans = 49798
</pre>
 
=={{header|Maxima}}==
<syntaxhighlight lang="maxima">
/* Function that return the terms of the Hofstadter Q sequence */
hofstadter(n):=block(
if member(n,[1,2]) then L[n]:1 else L[n]:L[n-L[n-1]]+L[n-L[n-2]],
L[n])$
 
/* Test cases */
/* First ten terms */
makelist(hofstadter(i),i,1,10);
 
/* 1000th term */
last(makelist(hofstadter(i),i,1,1000));
</syntaxhighlight>
{{out}}
<pre>
[1,1,2,3,3,4,5,5,6,6]
 
502
</pre>
 
=={{header|Modula-2}}==
<syntaxhighlight lang="modula2">MODULE QSequence;
FROM InOut IMPORT WriteString, WriteCard, WriteLn;
 
VAR n: CARDINAL;
Q: ARRAY [1..1000] OF CARDINAL;
BEGIN
Q[1] := 1;
Q[2] := 1;
FOR n := 3 TO 1000 DO
Q[n] := Q[n-Q[n-1]] + Q[n-Q[n-2]];
END;
WriteString("The first 10 terms are:");
FOR n := 1 TO 10 DO
WriteCard(Q[n],2);
END;
WriteLn();
WriteString("The 1000th term is:");
WriteCard(Q[1000],4);
WriteLn();
END QSequence.</syntaxhighlight>
{{out}}
<pre>The first 10 terms are: 1 1 2 3 3 4 5 5 6 6
The 1000th term is: 502</pre>
 
=={{header|MiniScript}}==
<langsyntaxhighlight MiniScriptlang="miniscript">cache = {1:1, 2:1}
 
Q = function(n)
Line 2,262 ⟶ 2,752:
print "Q(" + i + ") = " + Q(i)
end for
print "Q(1000) = " + Q(1000)</langsyntaxhighlight>
{{out}}
<pre>Q(1) = 1
Line 2,275 ⟶ 2,765:
Q(10) = 6
Q(1000) = 502</pre>
 
=={{header|Miranda}}==
<syntaxhighlight lang="miranda">main :: [sys_message]
main = [Stdout (lay (map showq ([1..10] ++ [1000])))]
where showq n = "q!" ++ show n ++ " = " ++ show (q!n)
 
q :: [num]
q = 0 : 1 : 1 : map f [3..] where f n = q!(n - q!(n-1)) + q!(n - q!(n-2))</syntaxhighlight>
{{out}}
<pre>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</pre>
 
=={{header|Nim}}==
<langsyntaxhighlight lang="nim">var q = @[1, 1]
for n in 2 ..< 100_000: q.add q[n-q[n-1]] + q[n-q[n-2]]
 
Line 2,290 ⟶ 2,800:
if q[n] < q[n-1]:
inc lessCount
echo lessCount</langsyntaxhighlight>
{{out}}
<pre>@[1, 1, 2, 3, 3, 4, 5, 5, 6, 6]
Line 2,298 ⟶ 2,808:
=={{header|Oberon-2}}==
Works with oo2c version 2
<langsyntaxhighlight lang="oberon2">
MODULE Hofstadter;
IMPORT
Line 2,335 ⟶ 2,845:
Out.String("terms less than the previous: ");Out.LongInt(count,4);Out.Ln
END Hofstadter.
</syntaxhighlight>
</lang>
Output:
<pre>
Line 2,352 ⟶ 2,862:
</pre>
 
=={{header|OforthOCaml}}==
<syntaxhighlight lang="ocaml">(* valid results for n in 0..119628 *)
let seq_hofstadter_q n =
let a = Bigarray.(Array1.create int16_unsigned c_layout n) in
let () =
for i = 0 to pred n do
a.{i} <- if i < 2 then 1 else a.{i - a.{pred i}} + a.{i - a.{i - 2}}
done
in
Seq.init n (Bigarray.Array1.get a)
 
let () =
<lang Oforth>: QSeqTask
let count_backflip (a, c) b = b, if b < a then succ c else c
and hq = seq_hofstadter_q 100_000 in
let () = Seq.(hq |> take 10 |> iter (Printf.printf " %u")) in
let () = Seq.(hq |> drop 999 |> take 1 |> iter (Printf.printf "\n%u\n")) in
hq |> Seq.fold_left count_backflip (0, 0) |> snd |> Printf.printf "%u\n"</syntaxhighlight>
{{out}}
<pre>
1 1 2 3 3 4 5 5 6 6
502
49798
</pre>
 
=={{header|Oforth}}==
<syntaxhighlight lang="oforth">: QSeqTask
| q i |
ListBuffer newSize(100000) dup add(1) dup add(1) ->q
Line 2,361 ⟶ 2,894:
q at(i) q at(i 1-) < ifTrue: [ 1+ ]
]
q left(10) println q at(1000) println println ; </langsyntaxhighlight>
 
{{out}}
Line 2,372 ⟶ 2,905:
=={{header|PARI/GP}}==
Straightforward, unoptimized version; about 1 ms.
<langsyntaxhighlight 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)"));</langsyntaxhighlight>
 
{{out}}
Line 2,382 ⟶ 2,915:
 
=={{header|Pascal}}==
<langsyntaxhighlight lang="pascal">Program HofstadterQSequence (output);
 
const
Line 2,405 ⟶ 2,938:
inc(flips);
writeln('Flips: ', flips);
end.</langsyntaxhighlight>
{{out}}
<pre>:> ./HofstadterQSequence
Line 2,415 ⟶ 2,948:
=={{header|Perl}}==
 
<langsyntaxhighlight Perllang="perl">my @Q = (0,1,1);
push @Q, $Q[-$Q[-1]] + $Q[-$Q[-2]] for 1..100_000;
say "First 10 terms: [@Q[1..10]]";
say "Term 1000: $Q[1000]";
say "Terms less than preceding in first 100k: ",scalar(grep { $Q[$_] < $Q[$_-1] } 2..100000);</langsyntaxhighlight>
{{out}}
<pre>First 10 terms: [1 1 2 3 3 4 5 5 6 6]
Line 2,426 ⟶ 2,959:
 
A more verbose and less idiomatic solution:
<langsyntaxhighlight Perllang="perl">#!/usr/bin/perl
use warnings;
use strict;
Line 2,447 ⟶ 2,980:
print "Up to and including the 100000'th term, $less_than_preceding terms are less " .
"than their preceding terms!\n";
</syntaxhighlight>
</lang>
{{out}}
<pre>1
Line 2,467 ⟶ 3,000:
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.
 
<langsyntaxhighlight Perllang="perl">#!perl
use strict;
use warnings;
Line 2,502 ⟶ 3,035:
}
print "Extra credit: $count\n";
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 2,513 ⟶ 3,046:
Just to be flash, I also (on the desktop only) calculated the 100 millionth term - the only limiting factor here is the length of Q
(theoretically 402,653,177 on 32 bit).
<!--<langsyntaxhighlight Phixlang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">Q</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}</span>
Line 2,526 ⟶ 3,060:
<span style="color: #0000FF;">{}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">q</span><span style="color: #0000FF;">(</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- (or collect one by one)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"First ten terms: %sv\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">sprint</span><span style="color: #0000FF;">(</span><span style="color: #000000;">Q</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">10</span><span style="color: #0000FF;">])})</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"1000th: %d\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">q</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1000</span><span style="color: #0000FF;">))</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"100,000th: %,d\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">q</span><span style="color: #0000FF;">(</span><span style="color: #000000;">100_000</span><span style="color: #0000FF;">))</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #000000;">100_000</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">n</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">Q</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]<</span><span style="color: #000000;">Q</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Flips up to 100,000: %,d\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">platform</span><span style="color: #0000FF;">()!=</span><span style="color: #004600;">JS</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"100,000,000th: %,d (%3.2fs)\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">q</span><span style="color: #0000FF;">(</span><span style="color: #000000;">100_000_000</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<!--</langsyntaxhighlight>-->
{{out}}
<pre>
First ten terms: {1,1,2,3,3,4,5,5,6,6}
1000th: 502
100,000th: 4815748,157
Flips up to 100,000: 4979849,798
100,000,000th: 5016650850,166,508 (78.53s52s)
</pre>
The last line shows fine under pwa/p2js, but would take about 20s.
 
=={{header|Picat}}==
<syntaxhighlight lang="picat">go =>
println([q(I) : I in 1..10]),
println(q1000=q(1000)),
Q = {q(I) : I in 1..100_000},
println(flips=sum({1 : I in 2..100_000, Q[I-1] > Q[I]})),
nl.
 
table
q(1) = 1.
q(2) = 1.
q(N) = q(N-q(N-1)) + q(N-q(N-2)).</syntaxhighlight>
 
{{out}}
<pre>[1,1,2,3,3,4,5,5,6,6]
q1000 = 502
flips = 49798</pre>
 
=={{header|PicoLisp}}==
<langsyntaxhighlight PicoLisplang="picolisp">(de q (N)
(cache '(NIL) N
(if (>= 2 N)
Line 2,555 ⟶ 3,108:
(+
(q (- N (q (dec N))))
(q (- N (q (- N 2)))) ) ) ) )</langsyntaxhighlight>
Test:
<langsyntaxhighlight PicoLisplang="picolisp">: (mapcar q (range 1 10))
-> (1 1 2 3 3 4 5 5 6 6)
 
Line 2,565 ⟶ 3,118:
: (let L (mapcar q (range 1 100000))
(cnt < (cdr L) L) )
-> 49798</langsyntaxhighlight>
 
=={{header|PL/I}}==
<syntaxhighlight lang="pl/i">
<lang PL/I>
/* Hofstrader Q sequence for any "n". */
 
Line 2,589 ⟶ 3,142:
end;
end H;
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 2,621 ⟶ 3,174:
</pre>
Bonus to produce the count of unordered values:
<syntaxhighlight lang="text">
declare tally fixed binary (31) initial (0);
 
Line 2,628 ⟶ 3,181:
end;
put skip data (tally);
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 2,634 ⟶ 3,187:
TALLY= 49798;
</pre>
 
=={{header|PL/M}}==
<syntaxhighlight lang="plm">100H:
BDOS: PROCEDURE (FN, ARG); DECLARE FN BYTE, ARG ADDRESS; GO TO 5; END BDOS;
EXIT: PROCEDURE; CALL BDOS(0,0); END EXIT;
PRINT: PROCEDURE (S); DECLARE S ADDRESS; CALL BDOS(9,S); END PRINT;
 
PRINT$NUMBER: PROCEDURE (N);
DECLARE S (7) BYTE INITIAL ('..... $');
DECLARE (N, P) ADDRESS, C BASED P BYTE;
P = .S(5);
DIGIT:
P = P - 1;
C = N MOD 10 + '0';
N = N / 10;
IF N > 0 THEN GO TO DIGIT;
CALL PRINT(P);
END PRINT$NUMBER;
 
DECLARE Q (1001) ADDRESS;
DECLARE N ADDRESS;
 
Q(1)=1;
Q(2)=1;
DO N=3 TO LAST(Q);
Q(N) = Q(N-Q(N-1)) + Q(N-Q(N-2));
END;
 
CALL PRINT(.'THE FIRST 10 TERMS ARE: $');
DO N=1 TO 10;
CALL PRINT$NUMBER(Q(N));
END;
 
CALL PRINT(.(13,10,'THE 1000TH TERM IS: $'));
CALL PRINT$NUMBER(Q(1000));
CALL EXIT;
EOF</syntaxhighlight>
{{out}}
<pre>THE FIRST 10 TERMS ARE: 1 1 2 3 3 4 5 5 6 6
THE 1000TH TERM IS: 502</pre>
 
=={{header|PureBasic}}==
<langsyntaxhighlight PureBasiclang="purebasic">If Not OpenConsole("Hofstadter Q sequence")
End 1
EndIf
Line 2,657 ⟶ 3,250:
PrintN(~"Flips:\t\t" + Str(flip))
Input()
End</langsyntaxhighlight>
{{out}}
<pre>First ten: 1 1 2 3 3 4 5 5 6 6
Line 2,664 ⟶ 3,257:
 
=={{header|Python}}==
<langsyntaxhighlight lang="python">def q(n):
if n < 1 or type(n) != int: raise ValueError("n must be an int >= 1")
try:
Line 2,679 ⟶ 3,272:
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))</langsyntaxhighlight>
 
;Extra credit:
Line 2,687 ⟶ 3,280:
 
The following code is to be concatenated to the code above:
<langsyntaxhighlight lang="python">from sys import getrecursionlimit
 
def q1(n):
Line 2,705 ⟶ 3,298:
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:])))</langsyntaxhighlight>
 
{{out|Combined output}}
Line 2,713 ⟶ 3,306:
 
===Alternative===
<langsyntaxhighlight lang="python">def q(n):
l = len(q.seq)
while l <= n:
Line 2,725 ⟶ 3,318:
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)]))</langsyntaxhighlight>
 
=={{header|Quackery}}==
 
<langsyntaxhighlight Quackerylang="quackery"> [ 2dup swap size dup 0negate <swap ifwithin 1+
abs swap size <
not if
[ drop size 1+ number$
Line 2,761 ⟶ 3,353:
say " decreasing terms" ]
bailed if
[ message take cr echo$ cr ]</langsyntaxhighlight>
 
{{out}}
Line 2,767 ⟶ 3,359:
<pre>1 1 2 3 3 4 5 5 6 6 ... 502
49798 decreasing terms</pre>
 
 
=={{header|R}}==
<langsyntaxhighlight lang="rsplus">
cache <- vector("integer", 0)
cache[1] <- 1
Line 2,798 ⟶ 3,389:
}
cat(count,"terms is less than its preceding term\n")
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 2,807 ⟶ 3,398:
 
=={{header|Racket}}==
<langsyntaxhighlight lang="racket">
#lang racket
 
Line 2,824 ⟶ 3,415:
;; extra credit
(for/sum ([i 100000]) (if (< (Q (add1 i)) (Q i)) 1 0))
</syntaxhighlight>
</lang>
 
{{out}}
Line 2,840 ⟶ 3,431:
Similar concept as the perl5 solution, except that the cache is only filled on demand.
 
<syntaxhighlight lang="raku" perl6line>class Hofstadter {
has @!c = 1,1;
method AT-POS ($me: Int $i) {
Line 2,858 ⟶ 3,449:
my $count = 0;
$count++ if $Q[$_ +1 ] < $Q[$_] for ^99_999;
say "In the first 100_000 terms, $count terms are less than their preceding terms";</langsyntaxhighlight>
{{out}}
<pre>first ten: 1 1 2 3 3 4 5 5 6 6
Line 2,867 ⟶ 3,458:
{{Works with|rakudo|2015-11-22}}
With a lazily generated array, we automatically get caching.
<syntaxhighlight lang="raku" perl6line>my @Q = 1, 1, -> $a, $b {
(state $n = 1)++;
@Q[$n - $a] + @Q[$n - $b]
Line 2,878 ⟶ 3,469:
say "In the first 100_000 terms, ",
[+](@Q[1..100000] Z< @Q[0..99999]),
" terms are less than their preceding terms";</langsyntaxhighlight>
(Same output.)
 
Line 2,884 ⟶ 3,475:
===non-recursive===
The REXX language doesn't allow expressions for stemmed array indices, so a temporary variable must be used.
<langsyntaxhighlight lang="rexx">/*REXX program generates the Hofstadter Q sequence for any specified N. */
parse arg a b c d . /*obtain optional arguments from the CL*/
if a=='' | a=="," then a= 10 /*Not specified? Then use the default.*/
Line 2,917 ⟶ 3,508:
/*──────────────────────────────────────────────────────────────────────────────────────*/
commas: parse arg _; do ?=length(_)-3 to 1 by -3; _=insert(',', _, ?); end; return _
th: procedure; #=abs(arg(1)); return word('th st nd rd',1+#//10*(#//100%10\==1)*(#//10<4))</langsyntaxhighlight>
{{out|output|text=&nbsp; when using the internal default inputs:}}
<pre>
Line 2,941 ⟶ 3,532:
This REXX example is identical to the first version
except that it uses a function to retrieve array elements which may have index expressions.
<langsyntaxhighlight lang="rexx">/*REXX program generates the Hofstadter Q sequence for any specified N. */
parse arg a b c d . /*obtain optional arguments from the CL*/
if a=='' | a=="," then a= 10 /*Not specified? Then use the default.*/
Line 2,972 ⟶ 3,563:
@: parse arg ?; return @.? /*return value of @.? to invoker.*/
th: procedure; #=abs(arg(1)); return word('th st nd rd',1+#//10*(#//100%10\==1)*(#//10<4))
commas: parse arg _; do ?=length(_)-3 to 1 by -3; _=insert(',', _, ?); end; return _</langsyntaxhighlight>
{{out|output|text=&nbsp; is identical to the 1<sup>st</sup> REXX version.}}
 
Line 2,978 ⟶ 3,569:
 
===recursive===
<langsyntaxhighlight lang="rexx">/*REXX program generates the Hofstadter Q sequence for any specified N. */
parse arg a b c d . /*obtain optional arguments from the CL*/
if a=='' | a=="," then a= 10 /*Not specified? Then use the default.*/
Line 3,012 ⟶ 3,603:
/*──────────────────────────────────────────────────────────────────────────────────────*/
th: procedure; #=abs(arg(1)); return word('th st nd rd',1+#//10*(#//100%10\==1)*(#//10<4))
commas: parse arg _; do ?=length(_)-3 to 1 by -3; _=insert(',', _, ?); end; return _</langsyntaxhighlight>
{{out|output|text=&nbsp; is identical to the 1<sup>st</sup> REXX version.}}
 
Line 3,018 ⟶ 3,609:
 
=={{header|Ring}}==
<langsyntaxhighlight lang="ring">
n = 20
aList = list(n)
Line 3,027 ⟶ 3,618:
if i <= 20 see "n = " + string(i) + " : "+ aList[i] + nl ok
next
</syntaxhighlight>
</lang>
 
=={{header|RPL}}==
{{works with|Halcyon Calc|4.2.7}}
{| class="wikitable"
! RPL code
! Comment
|-
|
≪
{ 1 1 } 3
WHILE '''DUP''' 4 PICK ≤ '''REPEAT'''
DUP2 2 - GETI ROT ROT GET → n q2 q1
≪ DUP n q1 - GET
OVER n q2 - GET + +
n 1 + SWAP
≫
'''END''' DROP
≫ ''''HOFST'''' STO
|
'''HOFST''' ''( m -- { Q(1)..Q(m) } ) ''
initialize stack with Q1, Q2 and loop index n
loop
store n, Q(n-2) and Q(n-1)
get Q(n-Q(n-1))
add Q(n-Q(n-2)) and add result to list
put back n+1 in stack
|}
{{in}}
<pre>
10 HOFST
1000 HOSFT DUP SIZE GET
</pre>
{{out}}
<pre>
2: { 1 1 2 3 3 4 5 5 6 6 }
1: 502
</pre>
 
=={{header|Ruby}}==
<langsyntaxhighlight lang="ruby">@cache = []
def Q(n)
if @cache[n].nil?
Line 3,051 ⟶ 3,682:
prev = q
end
puts "number of times in the first 100,000 terms where Q(i)<Q(i-1): #{count}"</langsyntaxhighlight>
{{out}}
<pre>first 10 numbers in the sequence: [1, 1, 2, 3, 3, 4, 5, 5, 6, 6]
Line 3,058 ⟶ 3,689:
 
=={{header|Run BASIC}}==
<langsyntaxhighlight Runbasiclang="runbasic">input "How many values do you want? :";n
dim Q(n)
Q(1) = 1
Line 3,068 ⟶ 3,699:
if i > 20 then print "n=";using("####",i);using("####",Q(i))
end
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 3,099 ⟶ 3,730:
Rust doesn't allow static Vec's (but there's lazy_static crate), thus memoization storage is allocated in <code>main</code>.
 
<langsyntaxhighlight lang="rust">fn hofq(q: &mut Vec<u32>, x : u32) -> u32 {
let cur_len=q.len()-1;
let i=x as usize;
Line 3,125 ⟶ 3,756:
println!("Term is less than preceding term {} times", nless);
}
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 3,147 ⟶ 3,778:
Naive but elegant version using only recursion doesn't work
because runtime is excessive increasing ...
<langsyntaxhighlight lang="scala">object HofstadterQseq extends App {
val Q: Int => Int = n => {
if (n <= 2) 1
Line 3,154 ⟶ 3,785:
(1 to 10).map(i=>(i,Q(i))).foreach(t=>println("Q("+t._1+") = "+t._2))
println("Q("+1000+") = "+Q(1000))
}</langsyntaxhighlight>
 
 
Line 3,161 ⟶ 3,792:
Thus we are forced to use a caching featured version.
 
<langsyntaxhighlight lang="scala">object HofstadterQseq extends App {
 
val HofQ = scala.collection.mutable.Map((1->1),(2->1))
Line 3,179 ⟶ 3,810:
println("Q("+1000+") = "+Q(1000))
println((3 to 100000).filter(i=>Q(i)<Q(i-1)).size)
}</langsyntaxhighlight>
{{out}}
<pre>Q(1) = 1
Line 3,198 ⟶ 3,829:
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.
<langsyntaxhighlight lang="lisp">(define qc '#(0 1 1))
(define filled 3)
(define len 3)
Line 3,244 ⟶ 3,875:
(if (>= i 100000) s
(loop (+ s (if (> (q i) (q (+ 1 i))) 1 0)) (+ 1 i)))))
(newline)</langsyntaxhighlight>
{{out}}
<pre>Q(1 .. 10): 1 1 2 3 3 4 5 5 6 6
Line 3,251 ⟶ 3,882:
 
=={{header|Seed7}}==
<langsyntaxhighlight lang="seed7">$ include "seed7_05.s7i";
 
const type: intHash is hash [integer] integer;
Line 3,288 ⟶ 3,919:
end for;
writeln("q(n) < q(n-1) for n = 2 .. 100000: " <& less_than_preceding);
end func;</langsyntaxhighlight>
 
{{out}}
Line 3,297 ⟶ 3,928:
q(n) < q(n-1) for n = 2 .. 100000: 49798
</pre>
 
=={{header|SETL}}==
<syntaxhighlight lang="setl">program hofstadter_q;
q := [1,1];
loop for n in [3..100000] do
q(n) := q(n-q(n-1)) + q(n-q(n-2));
end loop;
 
print("First 10 terms: " + q(1..10));
print("1000th term: " + q(1000));
print("q(x) < q(x-1): " + #[x : x in [2..#q] | q(x) < q(x-1)]);
end program;</syntaxhighlight>
{{out}}
<pre>First 10 terms: [1 1 2 3 3 4 5 5 6 6]
1000th term: 502
q(x) < q(x-1): 49798</pre>
 
=={{header|Sidef}}==
Using a memoized function:
<langsyntaxhighlight lang="ruby">func Q(n) is cached {
n <= 2 ? 1
 : Q(n - Q(n-1))+Q(n-Q(n-2))
Line 3,307 ⟶ 3,954:
say "First 10 terms: #{ {|n| Q(n) }.map(1..10) }"
say "Term 1000: #{Q(1000)}"
say "Terms less than preceding in first 100k: #{2..100000->count{|i|Q(i)<Q(i-1)}}"</langsyntaxhighlight>
 
Using an array:
<langsyntaxhighlight lang="ruby">var Q = [0, 1, 1]
100_000.times {
Q << (Q[-Q[-1]] + Q[-Q[-2]])
}
 
 
say "First 10 terms: #{Q.ftslice(1, ).first(10)}"
say "Term 1000: #{Q[1000]}"
say "Terms less than preceding in first 100k: #{2..100000->count{|i|Q[i]<Q[i-1]}}"</langsyntaxhighlight>
{{out}}
<pre>
Line 3,327 ⟶ 3,974:
=={{header|Swift}}==
{{trans|C}}
<langsyntaxhighlight lang="swift">let n = 100000
 
var q = Array(repeating: 0, count: n)
Line 3,346 ⟶ 3,993:
}
}
print("Number of times a member of the sequence is less than the preceding term for terms up to and including the 100,000th term: \(count)")</langsyntaxhighlight>
 
{{out}}
Line 3,356 ⟶ 4,003:
 
=={{header|Tailspin}}==
<langsyntaxhighlight lang="tailspin">
templates q
def outputFrom: $(1);
Line 3,385 ⟶ 4,032:
 
[[1, 100000] -> q] -> countDownSteps -> 'Less than previous $; times' -> !OUT::write
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 3,394 ⟶ 4,041:
 
=={{header|Tcl}}==
<langsyntaxhighlight lang="tcl">package require Tcl 8.5
 
# Index 0 is not used, but putting it in makes the code a bit shorter
Line 3,417 ⟶ 4,064:
incr count [expr {$q > [set q [expr {Q($i)}]]}]
}
puts "Q(i)<Q(i-1) for i \[2..100000\] is true $count times"</langsyntaxhighlight>
{{out}}
<pre>
Line 3,437 ⟶ 4,084:
{{trans|BBC BASIC}}
uBasic/4tH simply lacks the memory to make it through to the 1000th term. 256 is the best it can do.
<syntaxhighlight lang="text">Print "First 10 terms of Q = " ;
For i = 1 To 10 : Print FUNC(_q(i));" "; : Next : Print
Print "256th term = ";FUNC(_q(256))
Line 3,457 ⟶ 4,104:
Next
 
Return (@(a@-1))</langsyntaxhighlight>
{{out}}
<pre>First 10 terms of Q = 1 1 2 3 3 4 5 5 6 6
Line 3,465 ⟶ 4,112:
 
=={{header|VBA}}==
<langsyntaxhighlight lang="vb">Public Q(100000) As Long
Public Sub HofstadterQ()
Dim n As Long, smaller As Long
Line 3,481 ⟶ 4,128:
Debug.Print "The 1000th term is:"; Q(1000)
Debug.Print "Number of times smaller:"; smaller
End Sub</langsyntaxhighlight>{{out}}
<pre>First ten terms:
1 1 2 3 3 4 5 5 6 6
Line 3,488 ⟶ 4,135:
 
=={{header|VBScript}}==
<syntaxhighlight lang="vb">
<lang vb>
Sub q_sequence(n)
Dim Q()
Line 3,516 ⟶ 4,163:
 
q_sequence(100000)
</syntaxhighlight>
</lang>
 
{{Out}}
Line 3,526 ⟶ 4,173:
 
=={{header|Visual FoxPro}}==
<langsyntaxhighlight lang="vfp">
LOCAL p As Integer, i As Integer
CLEAR
Line 3,555 ⟶ 4,202:
RETURN aq[n]
ENDFUNC
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 3,566 ⟶ 4,213:
 
=={{header|Wren}}==
<langsyntaxhighlight ecmascriptlang="wren">var N = 1e5
var q = List.filled(N + 1, 0)
q[1] = 1
Line 3,579 ⟶ 4,226:
if (q[n] < q[n-1]) flips = flips + 1
}
System.print("\nThere are %(flips) flips in the first %(N) terms.")</langsyntaxhighlight>
 
{{out}}
Line 3,592 ⟶ 4,239:
 
=={{header|XPL0}}==
<langsyntaxhighlight XPL0lang="xpl0">code ChOut=8, CrLf=9, IntOut=11;
int N, C, Q(100_001);
[Q(1):= 1; Q(2):= 1; C:= 0;
Line 3,604 ⟶ 4,251:
IntOut(0, Q(1000)); CrLf(0);
IntOut(0, C); CrLf(0);
]</langsyntaxhighlight>
 
{{out}}
Line 3,615 ⟶ 4,262:
=={{header|zkl}}==
{{trans|ALGOL 68}}
<langsyntaxhighlight lang="zkl">const n = 0d100_000;
q:=(n+1).pump(List.createLong(n+1).write); // (0,1,2,...,n) base 1
q[1] = q[2] = 1;
Line 3,626 ⟶ 4,273:
flip := 0;
foreach i in (n){ flip += (q[i] > q[i + 1]) }
println("flips: ",flip);</langsyntaxhighlight>
{{out}}
<pre>
Line 3,637 ⟶ 4,284:
{{trans|BBC_BASIC}}
Extra credit 100000 is not implemented because of memory limitations.
<langsyntaxhighlight lang="zxbasic">10 PRINT "First 10 terms of Q = "
20 FOR i=1 TO 10: GO SUB 1000: PRINT s;" ";: NEXT i: PRINT
30 LET i=1000
Line 3,654 ⟶ 4,301:
1090 NEXT j
1100 LET s=q(i)
1110 RETURN</langsyntaxhighlight>
PureFox
9,476

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/203669...351205"