Hofstadter Q sequence: Difference between revisions
m
→{{header|Wren}}: Changed to Wren S/H
m (Forth - minor edit) |
m (→{{header|Wren}}: Changed to Wren S/H) |
||
(30 intermediate revisions by 18 users not shown) | |||
Line 24:
{{trans|C}}
<
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)</
{{out}}
Line 49:
=={{header|360 Assembly}}==
{{trans|PL/I}}
<
HOFSTRAD CSECT
USING HOFSTRAD,R15 set base register
Line 99:
Q DS 1000F array q(1000)
YREGS
END HOFSTRAD</
{{out}}
<pre style="height:16ex">
Line 117:
=={{header|8080 Assembly}}==
<
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</
{{out}}
Line 247:
=={{header|8086 Assembly}}==
<
cpu 8086
org 100h
Line 307:
num: db ' $'
Q: dw 1,1
</syntaxhighlight>
{{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}}==
<
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;</
{{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'''<
INT n = 100000;
Line 409 ⟶ 443:
printf(($"flips: "g(0)l$, flip))
)</
{{out}}
<pre>
Line 415 ⟶ 449:
502
flips: 49798
</pre>
=={{header|ALGOL-M}}==
<syntaxhighlight lang="algolm">begin
integer array Q[1:1000];
integer n;
Q[1] := Q[2] := 1;
for n := 3 step 1 until 1000 do
Q[n] := Q[n-Q[n-1]] + Q[n-Q[n-2]];
write("The first 10 terms are:");
write("");
for n := 1 step 1 until 10 do writeon(Q[n]);
write("The 1000th term is:", Q[1000]);
end</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|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}}==
<
size←100000
seq←{⍵,+/⍵[(1+⍴⍵)-¯2↑⍵]}⍣(size-2)⊢1 1
Line 426 ⟶ 528:
⎕←'The 1000th term is:', seq[1000]
⎕←(+/ 2>/seq),'terms were preceded by a larger term.'
∇</
{{out}}
Line 437 ⟶ 539:
=={{header|ARM Assembly}}==
<syntaxhighlight lang="text">.text
.global _start
_start: ldr r6,=qs @ R6 = base register for Q array
Line 550 ⟶ 652:
.align 4
.space 8 @ Buffer for number output
qs: .space 4 * 100001 @ One word per term</
{{out}}
Line 557 ⟶ 659:
The 1000th term is: 502
49798 terms were preceded by a larger term.</pre>
=={{header|Arturo}}==
<syntaxhighlight lang="rebol">q: new [1 1]
n: 2
while [n<1001][
'q ++ (get q n-q\[n-1]) + get q n-q\[n-2]
n: n+1
]
print ["First ten items:" first.n: 10 q]
print ["1000th item:" q\[999]]</syntaxhighlight>
{{out}}
<pre>First ten items: [1 1 2 3 3 4 5 5 6 6]
1000th item: 502</pre>
=={{header|AutoHotkey}}==
<
Q := HofsQSeq(100000)
Line 578 ⟶ 697:
}
return Q
}</
{{out}}
<pre>First ten: 1, 1, 2, 3, 3, 4, 5, 5, 6, 6,
Line 585 ⟶ 704:
=={{header|AWK}}==
<
BEGIN {
N = 100000
Line 606 ⟶ 725:
}
return seq
} </
<pre>Q-sequence(1..10) : 1 1 2 3 3 4 5 5 6 6
Line 612 ⟶ 731:
number of Q(n)<Q(n+1) for n<=100000 : 49798</pre>
=={{header|
==={{header|BASIC256}}===
{{trans|FreeBASIC}}
<syntaxhighlight lang="basic256">
limite = 100000
dim Q[limite+1]
Line 632 ⟶ 752:
print "Término número 1000: "; Q[1000]
print "Términos menores que los anteriores: "; cont
</syntaxhighlight>
{{out}}
<pre>
Line 638 ⟶ 758:
</pre>
==={{header|BBC BASIC}}===
<
FOR i% = 1 TO 10 : PRINT ;FNq(i%, c%) " "; : NEXT : PRINT
PRINT "1000th term = " ; FNq(1000, c%)
Line 656 ⟶ 776:
IF q%(i%) < q%(i%-1) THEN c% += 1
NEXT
= q%(n%)</
{{out}}
<pre>
Line 664 ⟶ 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}}==
<
& tbl$(memo,!memocells+1) { allocate array }
& ( Q
Line 697 ⟶ 926:
)
& out$!lessThan
);</
Output:
<pre>1 1 2 3 3 4 5 5 6 6
502
49798</pre>
=={{header|BCPL}}==
<syntaxhighlight lang="bcpl">get "libhdr"
let start() be
$( let Q = vec 1000
Q!1 := 1
Q!2 := 1
for n = 3 to 1000 do
Q!n := Q!(n-Q!(n-1)) + Q!(n-Q!(n-2))
writes("The first 10 terms are:")
for n = 1 to 10 do writef(" %N", Q!n)
writef("*NThe 1000th term is: %N*N", Q!1000)
$)</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|C}}==
<
#include <stdlib.h>
Line 727 ⟶ 976:
printf("flips: %d\n", flip);
return 0;
}</
{{out}}
<pre>1 1 2 3 3 4 5 5 6 6
Line 736 ⟶ 985:
=={{header|C sharp}}==
<
using System.Collections.Generic;
Line 799 ⟶ 1,048:
}
}
}</
{{out}}
Line 818 ⟶ 1,067:
solution modeled after Perl solution
<
int main() {
Line 837 ⟶ 1,086:
std::cout << less_than_preceding << " times a number was preceded by a greater number!" << std::endl;
return 0;
}</
{{out}}
<pre>The first 10 numbers are: 1 1 2 3 3 4 5 5 6 6
Line 847 ⟶ 1,096:
The subsequences are vectors for efficient indexing.
''qfirst'' iterates ''qs'' so the nth iteration is Q{1..n].
<
(let [n (count q)]
(condp = n
Line 859 ⟶ 1,108:
(println "first 10:" (qfirst 10))
(println "1000th:" (last (qfirst 1000)))
(println "extra credit:" (->> (qfirst 100000) (partition 2 1) (filter #(apply > %)) count))</
{{out}}
<syntaxhighlight lang="text">first 10: [1 1 2 3 3 4 5 5 6 6]
1000th: 502
extra credit: 49798</
=={{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}}
<
memo = [ 1 ,1, 1]
Q = (n) ->
Line 877 ⟶ 1,158:
# some results:
console.log 'Q(' + i + ') = ' + hofstadterQ(i) for i in [1..10]
console.log 'Q(1000) = ' + hofstadterQ(1000)</
{{out}}
<pre>Q(1) = 1
Line 889 ⟶ 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}}==
<
;;; generic memoization macro
Line 918 ⟶ 1,253:
(if (< next-q last-q) (incf c))
(setf last-q next-q))
finally (return c)))</
{{out}}
<pre>First of Q: (1 1 2 3 3 4 5 5 6 6)
Line 924 ⟶ 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:<
:initial-element 1
:adjustable t
Line 935 ⟶ 1,270:
(aref cc (- n (aref cc (- n 2)))))
cc))
(aref cc n)))</
=={{header|Cowgol}}==
<
# Generate 1000 terms of the Q sequence
Line 964 ⟶ 1,299:
print("The 1000th term is: ");
print_i16(Q[1000]);
print_nl();</
{{out}}
Line 972 ⟶ 1,307:
=={{header|D}}==
<
int Q(in int n) nothrow
Line 991 ⟶ 1,326:
iota(2, 100_001).count!(i => Q(i) < Q(i - 1)));
}
</syntaxhighlight>
{{out}}
<pre>Q(n) for n = [1..10] is: [1, 1, 2, 3, 3, 4, 5, 5, 6, 6]
Line 1,001 ⟶ 1,336:
{{trans|Python}}
Same output.
<
uint Q(in int n) nothrow
Line 1,020 ⟶ 1,355:
iota(2, 100_001).count!(i => Q(i) < Q(i - 1)));
}
</syntaxhighlight>
===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">
import std.stdio;
Line 1,057 ⟶ 1,392:
writefln("Q(i) is less than Q(i-1) for i [2..100_000] %d times.", lt);
}
</syntaxhighlight>
=={{header|Dart}}==
Naive version using only recursion (Q(1000) fails due to browser script runtime restrictions)
<
main() {
Line 1,068 ⟶ 1,403:
}
print("Q(1000)=${Q(1000)}");
}</
Version featuring caching.
<
Map<int,int> _table;
Line 1,112 ⟶ 1,447:
}
print("value is smaller than previous $count times");
}</
{{out}}
<pre>Q(1)=1
Line 1,128 ⟶ 1,463:
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;
Line 1,144 ⟶ 1,479:
print("Q(1000)=${q[1000]}");
print("value is smaller than previous $count times");
}</
=={{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}}==
<
(define RECURSE_BUMP 500) ;; minimum of chrome:500 safari:1000 firefox:2000
Line 1,171 ⟶ 1,557:
(Q 1000) → 502
(flips 100000) → 49798
</syntaxhighlight>
=={{header|Eiffel}}==
<syntaxhighlight lang="eiffel">
class
APPLICATION
Line 1,236 ⟶ 1,622:
end
</syntaxhighlight>
{{out}}
<pre>
Line 1,250 ⟶ 1,636:
{{trans|Erlang}}
changed collection (Erlang array => Map)
<
defp flip(v2, v1) when v1 > v2, do: 1
defp flip(_v2, _v1), do: 0
Line 1,273 ⟶ 1,659:
end
Hofstadter.main</
{{out}}
Line 1,283 ⟶ 1,669:
=={{header|Erlang}}==
<
%% Hofstadter Q Sequence for Rosetta Code
Line 1,313 ⟶ 1,699:
Acc = array:set(1, 1, Tmp),
hofstadter(?MAX, 2, Acc, 0).
</syntaxhighlight>
{{out}}
<pre>
Line 1,323 ⟶ 1,709:
=={{header|ERRE}}==
{{output|ERRE}}
<syntaxhighlight lang="erre">
PROGRAM HOFSTADER_Q
Line 1,359 ⟶ 1,745:
PRINT("Number of Q(n)<Q(n+1) for n<=10000 : ";NN)
END PROGRAM
</syntaxhighlight>
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===
<
// 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>
===The Tasks===
<
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>
{{out}}
<pre>
Line 1,380 ⟶ 1,823:
</pre>
===Extra Credit===
<
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>
{{out}}
<pre>
Line 1,389 ⟶ 1,832:
;What is a large number?
<
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>
{{out}}
<pre>
Line 1,401 ⟶ 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.
<
dup 2 tail* over length [ swap - ] curry map
[ dupd swap nth ] map 0 [ + ] reduce suffix ;
Line 1,407 ⟶ 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</
=={{header|Fermat}}==
<syntaxhighlight lang="text">Func Hq(n) = if n<2 then 1 else
Array qq[n+1];
qq[1] := 1;
Line 1,422 ⟶ 1,865:
for i=1 to 10 do !Hq(i);!' ' od;
Hq(1000)</
{{out}}<pre>
1 1 2 3 3 4 5 5 6 6
Line 1,429 ⟶ 1,872:
=={{header|Forth}}==
{{trans|C}}
<
: q ( n -- addr ) cells here + ;
Line 1,455 ⟶ 1,898:
999 q @ . cr
flips
bye</
{{out}}
Line 1,467 ⟶ 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">
Calculate the Hofstadter Q-sequence, using a big array rather than recursion.
INTEGER ENUFF
Line 1,498 ⟶ 1,941:
999 WRITE (6,*) "Bye."
END
</syntaxhighlight>
Output:
Line 1,512 ⟶ 1,955:
=={{header|FreeBASIC}}==
<
Const limite = 100000
Line 1,534 ⟶ 1,977:
Print "Terminos menores que los anteriores: " &cont
End
</syntaxhighlight>
{{out}}
<pre>
Line 1,544 ⟶ 1,987:
=={{header|Fōrmulæ}}==
'''Solution'''
The following function calculate the given number of terms of the Hofstadter Q sequence:
[[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.
<
import "fmt"
Line 1,597 ⟶ 2,060:
func showQ(n int) {
fmt.Printf("Q(%d) = %d\n", n, q(n))
}</
{{out}}
<pre>
Line 1,616 ⟶ 2,079:
=={{header|GW-BASIC}}==
<
20 Q(1) = 1: Q(2) = 1
30 FOR N = 3 TO 1000
Line 1,624 ⟶ 2,087:
70 PRINT Q(N)
80 NEXT N
90 PRINT Q(1000)</
=={{header|Haskell}}==
Line 1,630 ⟶ 2,093:
The basic task:
<
qq = 0 : 1 : 1 : map g [3..]
g n = qq !! (n - qq !! (n-1)) + qq !! (n - qq !! (n-2))
Line 1,637 ⟶ 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)</
Extra credit task:
<
qSequence n = arr
Line 1,661 ⟶ 2,124:
. _S (zipWith (-)) tail . take n . elems $ arr )
_S f g x = f x (g x)</
{{out}}
<
([1,1,2,3,3,4,5,5,6,6],502,49798)
(0.09 secs, 18879708 bytes)
Line 1,670 ⟶ 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)</
Using a list (more or less) seemlessly backed up by a double resizing array:
<
qq ar n = (arr!n) : qq arr (n+1) where
l = snd (bounds ar)
Line 1,688 ⟶ 2,151:
putStr("1000-th: "); print (q !! 999)
putStr("flips: ")
print $ length $ filter id $ take 100000 (zipWith (>) q (tail q))</
{{out}}
<pre>
Line 1,697 ⟶ 2,160:
List backed up by a list of arrays, with nominal constant lookup time. ''Somehow'' faster than the previous method.
<
import Data.Int (Int64)
Line 1,717 ⟶ 2,180:
where
qqq :: [Int64]
qqq = map fromIntegral $ take 3000000 q</
=={{header|Icon}} and {{header|Unicon}}==
<
procedure main()
Line 1,758 ⟶ 2,221:
runerr(500,n)
}
end</
{{libheader|Icon Programming Library}}
Line 1,777 ⟶ 2,240:
=={{header|IS-BASIC}}==
<
110 LET LIMIT=1000
120 NUMERIC Q(1 TO LIMIT)
Line 1,788 ⟶ 2,251:
190 PRINT Q(I);
200 NEXT
210 PRINT :PRINT "Term 1000:";Q(1000)</
=={{header|J}}==
'''Solution''' (''bottom-up''):<
Q=: verb define
n=. >./,y
Line 1,798 ⟶ 2,261:
end.
y{Qs
)</
'''Solution''' (''top-down''):<
'''Example''':<
1 1 2 3 3 4 5 5 6 6
Q 1000
502
+/2>/\ Q 1+i.100000
49798</
'''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,818 ⟶ 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.
<
import java.util.Map;
Line 1,863 ⟶ 2,326:
System.out.println("Q(" + maxN + ") was called the most with " + maxUses + " calls");
}
}</
{{out}}
<pre>Q(1) = 1
Line 1,882 ⟶ 2,345:
===ES5===
Based on memoization example from 'JavaScript: The Good Parts'.
<
var memo = [1,1,1];
var Q = function (n) {
Line 1,900 ⟶ 2,363:
console.log('Q(1000) = ' + hofstadterQ(1000));
</syntaxhighlight>
{{out}}
<pre>
Line 1,918 ⟶ 2,381:
===ES6===
Memoising with the accumulator of a fold
<
'use strict';
Line 1,957 ⟶ 2,420:
.reduce((a, x, i, xs) => x < xs[i - 1] ? a + 1 : a, 0)
};
})();</
{{Out}}
<
"thousandth":502,
"Q<Q-1UpTo10E5":49798}</
=={{header|jq}}==
Line 1,970 ⟶ 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">
# For n>=2, Q(n) = Q(n - Q(n-1)) + Q(n - Q(n-2))
def Q:
Line 1,998 ⟶ 2,461:
((range(0;11), 1000) | "Q(\(.)) = \( . | Q)"),
(100000 | "flips(\(.)) = \(flips(.))")</
===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
Line 2,020 ⟶ 2,483:
real 0m0.562s
user 0m0.541s
sys 0m0.011s</
=={{header|Julia}}==
The following implementation accepts an argument that is a single integer, an array of integers, or a range:
<
nmax = maximum(n)
r = Vector{typerst}(nmax)
Line 2,037 ⟶ 2,500:
println("First ten elements of sequence: ", join(hofstQseq(1:10), ", "))
println("1000-th element: ", hofstQseq(1000))
</syntaxhighlight>
{{out}}
Line 2,044 ⟶ 2,507:
And we can also count the number of times a value is less than its predecessor by, for example:
<
cnt = count(diff(seq) .< 0)
println("$cnt elements are less than the preceding one.")</
{{out}}
Line 2,054 ⟶ 2,517:
=={{header|Kotlin}}==
<
fun main(args: Array<String>) {
Line 2,066 ⟶ 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")
}</
{{out}}
Line 2,077 ⟶ 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}}==
<
VECTOR VALUES FMT = $2HQ(,I4,3H) =,I4*$
Line 2,092 ⟶ 2,590:
PRINT FORMAT FMT, 1000, Q(1000)
END OF PROGRAM</
{{out}}
Line 2,112 ⟶ 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.
<
option remember, system;
if n = 1 or n = 2 then
Line 2,119 ⟶ 2,617:
thisproc( n - thisproc( n - 1 ) ) + thisproc( n - thisproc( n - 2 ) )
end if
end proc:</
From this we get:
<
1, 1, 2, 3, 3, 4, 5, 5, 6, 6
> Q( 1000 );
502</
To determine the number of "flips", we proceed as follows.
<
> for i from 2 to 100000 do
> if L[ i ] < L[ i - 1 ] then
Line 2,134 ⟶ 2,632:
> end do:
> flips;
49798</
Alternatively, we can build the sequence in an array.
<
local a := Array( 1 .. n );
a[ 1 ] := 1;
Line 2,150 ⟶ 2,648:
end do;
flips
end proc:</
This gives the same result.
<
49798</
=={{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]
49798</
=={{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)];
Line 2,176 ⟶ 2,674:
Q(n) = Q(n-Q(n-1))+Q(n-Q(n-2));
end;
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)
Line 2,190 ⟶ 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}}==
<
Q = function(n)
Line 2,205 ⟶ 2,752:
print "Q(" + i + ") = " + Q(i)
end for
print "Q(1000) = " + Q(1000)</
{{out}}
<pre>Q(1) = 1
Line 2,218 ⟶ 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}}==
<
for n in 2 ..< 100_000: q.add q[n-q[n-1]] + q[n-q[n-2]]
Line 2,233 ⟶ 2,800:
if q[n] < q[n-1]:
inc lessCount
echo lessCount</
{{out}}
<pre>@[1, 1, 2, 3, 3, 4, 5, 5, 6, 6]
Line 2,241 ⟶ 2,808:
=={{header|Oberon-2}}==
Works with oo2c version 2
<
MODULE Hofstadter;
IMPORT
Line 2,278 ⟶ 2,845:
Out.String("terms less than the previous: ");Out.LongInt(count,4);Out.Ln
END Hofstadter.
</syntaxhighlight>
Output:
<pre>
Line 2,295 ⟶ 2,862:
</pre>
=={{header|
<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 () =
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,304 ⟶ 2,894:
q at(i) q at(i 1-) < ifTrue: [ 1+ ]
]
q left(10) println q at(1000) println println ; </
{{out}}
Line 2,315 ⟶ 2,905:
=={{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)"));
print("1000-th term: "Q[1000],if(Q[1000]==502," (as expected)"," (in error)"));</
{{out}}
Line 2,325 ⟶ 2,915:
=={{header|Pascal}}==
<
const
Line 2,348 ⟶ 2,938:
inc(flips);
writeln('Flips: ', flips);
end.</
{{out}}
<pre>:> ./HofstadterQSequence
Line 2,358 ⟶ 2,948:
=={{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]";
say "Terms less than preceding in first 100k: ",scalar(grep { $Q[$_] < $Q[$_-1] } 2..100000);</
{{out}}
<pre>First 10 terms: [1 1 2 3 3 4 5 5 6 6]
Line 2,369 ⟶ 2,959:
A more verbose and less idiomatic solution:
<
use warnings;
use strict;
Line 2,390 ⟶ 2,980:
print "Up to and including the 100000'th term, $less_than_preceding terms are less " .
"than their preceding terms!\n";
</syntaxhighlight>
{{out}}
<pre>1
Line 2,410 ⟶ 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.
<
use strict;
use warnings;
Line 2,445 ⟶ 3,035:
}
print "Extra credit: $count\n";
</syntaxhighlight>
{{out}}
<pre>
Line 2,454 ⟶ 3,044:
=={{header|Phix}}==
Just to be flash, I also (on the desktop only) calculated the 100 millionth term - the only limiting factor here
(
<!--<syntaxhighlight lang="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>
<span style="color: #008080;">function</span> <span style="color: #000000;">q</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: #004080;">integer</span> <span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">Q</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">></span><span style="color: #000000;">l</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">l</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #000000;">Q</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">Q</span><span style="color: #0000FF;">[</span><span style="color: #000000;">l</span><span style="color: #0000FF;">-</span><span style="color: #000000;">Q</span><span style="color: #0000FF;">[</span><span style="color: #000000;">l</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]]+</span><span style="color: #000000;">Q</span><span style="color: #0000FF;">[</span><span style="color: #000000;">l</span><span style="color: #0000FF;">-</span><span style="color: #000000;">Q</span><span style="color: #0000FF;">[</span><span style="color: #000000;">l</span><span style="color: #0000FF;">-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">Q</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<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: %v\n"</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>
<!--</syntaxhighlight>-->
{{out}}
<pre>
First ten terms: {1,1,2,3,3,4,5,5,6,6}
1000th: 502
100,000th:
Flips up to 100,000:
100,000,000th:
</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}}==
<
(cache '(NIL) N
(if (>= 2 N)
Line 2,494 ⟶ 3,108:
(+
(q (- N (q (dec N))))
(q (- N (q (- N 2)))) ) ) ) )</
Test:
<
-> (1 1 2 3 3 4 5 5 6 6)
Line 2,504 ⟶ 3,118:
: (let L (mapcar q (range 1 100000))
(cnt < (cdr L) L) )
-> 49798</
=={{header|PL/I}}==
<syntaxhighlight lang="pl/i">
/* Hofstrader Q sequence for any "n". */
Line 2,528 ⟶ 3,142:
end;
end H;
</syntaxhighlight>
{{out}}
<pre>
Line 2,560 ⟶ 3,174:
</pre>
Bonus to produce the count of unordered values:
<syntaxhighlight lang="text">
declare tally fixed binary (31) initial (0);
Line 2,567 ⟶ 3,181:
end;
put skip data (tally);
</syntaxhighlight>
{{out}}
<pre>
Line 2,573 ⟶ 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}}==
<
End 1
EndIf
Line 2,596 ⟶ 3,250:
PrintN(~"Flips:\t\t" + Str(flip))
Input()
End</
{{out}}
<pre>First ten: 1 1 2 3 3 4 5 5 6 6
Line 2,603 ⟶ 3,257:
=={{header|Python}}==
<
if n < 1 or type(n) != int: raise ValueError("n must be an int >= 1")
try:
Line 2,618 ⟶ 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))</
;Extra credit:
Line 2,626 ⟶ 3,280:
The following code is to be concatenated to the code above:
<
def q1(n):
Line 2,644 ⟶ 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:])))</
{{out|Combined output}}
Line 2,652 ⟶ 3,306:
===Alternative===
<
l = len(q.seq)
while l <= n:
Line 2,664 ⟶ 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)]))</
=={{header|Quackery}}==
<syntaxhighlight lang="quackery">[ 2dup swap size dup negate swap within
not if
[ drop size 1+ number$
$ "Term " swap join
$ " of the Q sequence is not defined."
join message put bail ]
peek ] is qpeek ( [ n --> x )
[ dup dup -1 qpeek negate qpeek
dip [ dup dup -2 qpeek negate qpeek ]
+ join ] is next-q ( [ --> [ )
[ dup size 2 < iff
[ drop 0 ] done
0 swap behead swap
witheach
[ tuck > if [ dip 1+ ] ]
drop ] is drops ( [ --> n )
0 backup
[ ' [ 1 1 ]
998 times next-q
dup
-1 split swap 10 split drop
witheach [ echo sp ]
say "... "
0 peek echo cr
99000 times next-q
drops echo
say " decreasing terms" ]
bailed if
[ message take cr echo$ cr ]</syntaxhighlight>
{{out}}
<pre>1 1 2 3 3 4 5 5 6 6 ... 502
49798 decreasing terms</pre>
=={{header|R}}==
<
cache <- vector("integer", 0)
cache[1] <- 1
Line 2,695 ⟶ 3,389:
}
cat(count,"terms is less than its preceding term\n")
</syntaxhighlight>
{{out}}
<pre>
Line 2,704 ⟶ 3,398:
=={{header|Racket}}==
<
#lang racket
Line 2,721 ⟶ 3,415:
;; extra credit
(for/sum ([i 100000]) (if (< (Q (add1 i)) (Q i)) 1 0))
</syntaxhighlight>
{{out}}
Line 2,737 ⟶ 3,431:
Similar concept as the perl5 solution, except that the cache is only filled on demand.
<syntaxhighlight lang="raku"
has @!c = 1,1;
method AT-POS ($me: Int $i) {
Line 2,755 ⟶ 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";</
{{out}}
<pre>first ten: 1 1 2 3 3 4 5 5 6 6
Line 2,764 ⟶ 3,458:
{{Works with|rakudo|2015-11-22}}
With a lazily generated array, we automatically get caching.
<syntaxhighlight lang="raku"
(state $n = 1)++;
@Q[$n - $a] + @Q[$n - $b]
Line 2,775 ⟶ 3,469:
say "In the first 100_000 terms, ",
[+](@Q[1..100000] Z< @Q[0..99999]),
" terms are less than their preceding terms";</
(Same output.)
Line 2,781 ⟶ 3,475:
===non-recursive===
The REXX language doesn't allow expressions for stemmed array indices, so a temporary variable must be used.
<
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,814 ⟶ 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))</
{{out|output|text= when using the internal default inputs:}}
<pre>
Line 2,838 ⟶ 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.
<
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,869 ⟶ 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 _</
{{out|output|text= is identical to the 1<sup>st</sup> REXX version.}}
Line 2,875 ⟶ 3,569:
===recursive===
<
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,909 ⟶ 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 _</
{{out|output|text= is identical to the 1<sup>st</sup> REXX version.}}
Line 2,915 ⟶ 3,609:
=={{header|Ring}}==
<
n = 20
aList = list(n)
Line 2,924 ⟶ 3,618:
if i <= 20 see "n = " + string(i) + " : "+ aList[i] + nl ok
next
</syntaxhighlight>
=={{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}}==
<
def Q(n)
if @cache[n].nil?
Line 2,948 ⟶ 3,682:
prev = q
end
puts "number of times in the first 100,000 terms where Q(i)<Q(i-1): #{count}"</
{{out}}
<pre>first 10 numbers in the sequence: [1, 1, 2, 3, 3, 4, 5, 5, 6, 6]
Line 2,955 ⟶ 3,689:
=={{header|Run BASIC}}==
<
dim Q(n)
Q(1) = 1
Line 2,965 ⟶ 3,699:
if i > 20 then print "n=";using("####",i);using("####",Q(i))
end
</syntaxhighlight>
{{out}}
<pre>
Line 2,996 ⟶ 3,730:
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;
Line 3,022 ⟶ 3,756:
println!("Term is less than preceding term {} times", nless);
}
</syntaxhighlight>
{{out}}
<pre>
Line 3,044 ⟶ 3,778:
Naive but elegant version using only recursion doesn't work
because runtime is excessive increasing ...
<
val Q: Int => Int = n => {
if (n <= 2) 1
Line 3,051 ⟶ 3,785:
(1 to 10).map(i=>(i,Q(i))).foreach(t=>println("Q("+t._1+") = "+t._2))
println("Q("+1000+") = "+Q(1000))
}</
Line 3,058 ⟶ 3,792:
Thus we are forced to use a caching featured version.
<
val HofQ = scala.collection.mutable.Map((1->1),(2->1))
Line 3,076 ⟶ 3,810:
println("Q("+1000+") = "+Q(1000))
println((3 to 100000).filter(i=>Q(i)<Q(i-1)).size)
}</
{{out}}
<pre>Q(1) = 1
Line 3,095 ⟶ 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.
<
(define filled 3)
(define len 3)
Line 3,141 ⟶ 3,875:
(if (>= i 100000) s
(loop (+ s (if (> (q i) (q (+ 1 i))) 1 0)) (+ 1 i)))))
(newline)</
{{out}}
<pre>Q(1 .. 10): 1 1 2 3 3 4 5 5 6 6
Line 3,148 ⟶ 3,882:
=={{header|Seed7}}==
<
const type: intHash is hash [integer] integer;
Line 3,185 ⟶ 3,919:
end for;
writeln("q(n) < q(n-1) for n = 2 .. 100000: " <& less_than_preceding);
end func;</
{{out}}
Line 3,194 ⟶ 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:
<
n <= 2 ? 1
: Q(n - Q(n-1))+Q(n-Q(n-2))
Line 3,204 ⟶ 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)}}"</
Using an array:
<
100_000.times {
Q << (Q[-Q[-1]] + Q[-Q[-2]])
}
say "First 10 terms: #{Q.
say "Term 1000: #{Q[1000]}"
say "Terms less than preceding in first 100k: #{2..100000->count{|i|Q[i]<Q[i-1]}}"</
{{out}}
<pre>
Line 3,224 ⟶ 3,974:
=={{header|Swift}}==
{{trans|C}}
<
var q = Array(repeating: 0, count: n)
Line 3,243 ⟶ 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)")</
{{out}}
Line 3,253 ⟶ 4,003:
=={{header|Tailspin}}==
<
templates q
def outputFrom: $(1);
Line 3,282 ⟶ 4,032:
[[1, 100000] -> q] -> countDownSteps -> 'Less than previous $; times' -> !OUT::write
</syntaxhighlight>
{{out}}
<pre>
Line 3,291 ⟶ 4,041:
=={{header|Tcl}}==
<
# Index 0 is not used, but putting it in makes the code a bit shorter
Line 3,314 ⟶ 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"</
{{out}}
<pre>
Line 3,334 ⟶ 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,354 ⟶ 4,104:
Next
Return (@(a@-1))</
{{out}}
<pre>First 10 terms of Q = 1 1 2 3 3 4 5 5 6 6
Line 3,362 ⟶ 4,112:
=={{header|VBA}}==
<
Public Sub HofstadterQ()
Dim n As Long, smaller As Long
Line 3,378 ⟶ 4,128:
Debug.Print "The 1000th term is:"; Q(1000)
Debug.Print "Number of times smaller:"; smaller
End Sub</
<pre>First ten terms:
1 1 2 3 3 4 5 5 6 6
Line 3,385 ⟶ 4,135:
=={{header|VBScript}}==
<syntaxhighlight lang="vb">
Sub q_sequence(n)
Dim Q()
Line 3,413 ⟶ 4,163:
q_sequence(100000)
</syntaxhighlight>
{{Out}}
Line 3,423 ⟶ 4,173:
=={{header|Visual FoxPro}}==
<
LOCAL p As Integer, i As Integer
CLEAR
Line 3,452 ⟶ 4,202:
RETURN aq[n]
ENDFUNC
</syntaxhighlight>
{{out}}
<pre>
Line 3,463 ⟶ 4,213:
=={{header|Wren}}==
<
var q = List.filled(N + 1, 0)
q[1] = 1
Line 3,476 ⟶ 4,226:
if (q[n] < q[n-1]) flips = flips + 1
}
System.print("\nThere are %(flips) flips in the first %(N) terms.")</
{{out}}
Line 3,489 ⟶ 4,239:
=={{header|XPL0}}==
<
int N, C, Q(100_001);
[Q(1):= 1; Q(2):= 1; C:= 0;
Line 3,501 ⟶ 4,251:
IntOut(0, Q(1000)); CrLf(0);
IntOut(0, C); CrLf(0);
]</
{{out}}
Line 3,512 ⟶ 4,262:
=={{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;
Line 3,523 ⟶ 4,273:
flip := 0;
foreach i in (n){ flip += (q[i] > q[i + 1]) }
println("flips: ",flip);</
{{out}}
<pre>
Line 3,534 ⟶ 4,284:
{{trans|BBC_BASIC}}
Extra credit 100000 is not implemented because of memory limitations.
<
20 FOR i=1 TO 10: GO SUB 1000: PRINT s;" ";: NEXT i: PRINT
30 LET i=1000
Line 3,551 ⟶ 4,301:
1090 NEXT j
1100 LET s=q(i)
1110 RETURN</
|