Hofstadter Q sequence: Difference between revisions
m
→{{header|Wren}}: Changed to Wren S/H
m (→{{header|Phix}}: added commas to output) |
m (→{{header|Wren}}: Changed to Wren S/H) |
||
(15 intermediate revisions by 13 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 315:
=={{header|Action!}}==
<
DEFINE MAX="1000"
INT ARRAY q(MAX+1)
Line 331:
OD
PrintF("%I: %I%E",MAX,q(MAX))
RETURN</
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Hofstadter_Q_sequence.png Screenshot from Atari 8-bit computer]
Line 349:
=={{header|Ada}}==
<
procedure Hofstadter_Q_Sequence is
Line 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 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 443:
printf(($"flips: "g(0)l$, flip))
)</
{{out}}
<pre>
Line 452:
=={{header|ALGOL-M}}==
<
integer array Q[1:1000];
integer n;
Line 465:
write("The 1000th term is:", Q[1000]);
end</
{{out}}
<pre>The first 10 terms are:
Line 472:
=={{header|ALGOL W}}==
<
% Q(n) = Q( n - Q( n - 1 ) ) + Q( n - Q( n - 2 ) ) for n > 2 %
integer MAX_Q;
Line 510:
write( i_w := 1, s_w := 0, "Q(n) < Q(n-1) ", ltCount," times for n up to ", MAX_Q )
end
end.</
{{out}}
<pre>
Line 521:
=={{header|APL}}==
<
size←100000
seq←{⍵,+/⍵[(1+⍴⍵)-¯2↑⍵]}⍣(size-2)⊢1 1
Line 528:
⎕←'The 1000th term is:', seq[1000]
⎕←(+/ 2>/seq),'terms were preceded by a larger term.'
∇</
{{out}}
Line 539:
=={{header|ARM Assembly}}==
<syntaxhighlight lang="text">.text
.global _start
_start: ldr r6,=qs @ R6 = base register for Q array
Line 652:
.align 4
.space 8 @ Buffer for number output
qs: .space 4 * 100001 @ One word per term</
{{out}}
Line 662:
=={{header|Arturo}}==
<
n: 2
while [n<1001][
Line 670:
print ["First ten items:" first.n: 10 q]
print ["1000th item:" q\[999]]</
{{out}}
Line 678:
=={{header|AutoHotkey}}==
<
Q := HofsQSeq(100000)
Line 697:
}
return Q
}</
{{out}}
<pre>First ten: 1, 1, 2, 3, 3, 4, 5, 5, 6, 6,
Line 704:
=={{header|AWK}}==
<
BEGIN {
N = 100000
Line 725:
}
return seq
} </
<pre>Q-sequence(1..10) : 1 1 2 3 3 4 5 5 6 6
Line 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 751 ⟶ 752:
print "Término número 1000: "; Q[1000]
print "Términos menores que los anteriores: "; cont
</syntaxhighlight>
{{out}}
<pre>
Line 757 ⟶ 758:
</pre>
==={{header|BBC BASIC}}===
<
FOR i% = 1 TO 10 : PRINT ;FNq(i%, c%) " "; : NEXT : PRINT
PRINT "1000th term = " ; FNq(1000, c%)
Line 775 ⟶ 776:
IF q%(i%) < q%(i%-1) THEN c% += 1
NEXT
= q%(n%)</
{{out}}
<pre>
Line 783 ⟶ 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 816 ⟶ 926:
)
& out$!lessThan
);</
Output:
<pre>1 1 2 3 3 4 5 5 6 6
Line 823 ⟶ 933:
=={{header|BCPL}}==
<
let start() be
Line 837 ⟶ 947:
writef("*NThe 1000th term is: %N*N", Q!1000)
$)</
{{out}}
<pre>The first 10 terms are: 1 1 2 3 3 4 5 5 6 6
Line 843 ⟶ 953:
=={{header|C}}==
<
#include <stdlib.h>
Line 866 ⟶ 976:
printf("flips: %d\n", flip);
return 0;
}</
{{out}}
<pre>1 1 2 3 3 4 5 5 6 6
Line 875 ⟶ 985:
=={{header|C sharp}}==
<
using System.Collections.Generic;
Line 938 ⟶ 1,048:
}
}
}</
{{out}}
Line 957 ⟶ 1,067:
solution modeled after Perl solution
<
int main() {
Line 976 ⟶ 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 986 ⟶ 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 998 ⟶ 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}}==
<
q: array[int] := array[int]$[1,1]
for i: int in int$from_to(3,n) do
Line 1,030 ⟶ 1,140:
stream$putl(po, "\nflips: " || int$unparse(flips))
end start_up</
{{out}}
<pre>First 10 terms: 1 1 2 3 3 4 5 5 6 6
Line 1,038 ⟶ 1,148:
=={{header|CoffeeScript}}==
{{trans|JavaScript}}
<
memo = [ 1 ,1, 1]
Q = (n) ->
Line 1,048 ⟶ 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 1,063 ⟶ 1,173:
=={{header|COBOL}}==
<
PROGRAM-ID. Q-SEQ.
Line 1,102 ⟶ 1,212:
MOVE N TO IX.
MOVE Q(N) TO ITEM.
DISPLAY 'Q(' IX ') = ' ITEM.</
{{out}}
<pre>Q( 1) = 1
Line 1,117 ⟶ 1,227:
=={{header|Common Lisp}}==
<
;;; generic memoization macro
Line 1,143 ⟶ 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 1,149 ⟶ 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 1,160 ⟶ 1,270:
(aref cc (- n (aref cc (- n 2)))))
cc))
(aref cc n)))</
=={{header|Cowgol}}==
<
# Generate 1000 terms of the Q sequence
Line 1,189 ⟶ 1,299:
print("The 1000th term is: ");
print_i16(Q[1000]);
print_nl();</
{{out}}
Line 1,197 ⟶ 1,307:
=={{header|D}}==
<
int Q(in int n) nothrow
Line 1,216 ⟶ 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,226 ⟶ 1,336:
{{trans|Python}}
Same output.
<
uint Q(in int n) nothrow
Line 1,245 ⟶ 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,282 ⟶ 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,293 ⟶ 1,403:
}
print("Q(1000)=${Q(1000)}");
}</
Version featuring caching.
<
Map<int,int> _table;
Line 1,337 ⟶ 1,447:
}
print("value is smaller than previous $count times");
}</
{{out}}
<pre>Q(1)=1
Line 1,353 ⟶ 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,369 ⟶ 1,479:
print("Q(1000)=${q[1000]}");
print("value is smaller than previous $count times");
}</
=={{header|Draco}}==
<
word n;
q[1] := 1;
Line 1,391 ⟶ 1,501:
writeln();
writeln("The 1000th term is: ", q[1000])
corp</
{{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,421 ⟶ 1,557:
(Q 1000) → 502
(flips 100000) → 49798
</syntaxhighlight>
=={{header|Eiffel}}==
<syntaxhighlight lang="eiffel">
class
APPLICATION
Line 1,486 ⟶ 1,622:
end
</syntaxhighlight>
{{out}}
<pre>
Line 1,500 ⟶ 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,523 ⟶ 1,659:
end
Hofstadter.main</
{{out}}
Line 1,533 ⟶ 1,669:
=={{header|Erlang}}==
<
%% Hofstadter Q Sequence for Rosetta Code
Line 1,563 ⟶ 1,699:
Acc = array:set(1, 1, Tmp),
hofstadter(?MAX, 2, Acc, 0).
</syntaxhighlight>
{{out}}
<pre>
Line 1,573 ⟶ 1,709:
=={{header|ERRE}}==
{{output|ERRE}}
<syntaxhighlight lang="erre">
PROGRAM HOFSTADER_Q
Line 1,609 ⟶ 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,630 ⟶ 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,639 ⟶ 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,651 ⟶ 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,657 ⟶ 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,672 ⟶ 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,679 ⟶ 1,872:
=={{header|Forth}}==
{{trans|C}}
<
: q ( n -- addr ) cells here + ;
Line 1,705 ⟶ 1,898:
999 q @ . cr
flips
bye</
{{out}}
Line 1,717 ⟶ 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,748 ⟶ 1,941:
999 WRITE (6,*) "Bye."
END
</syntaxhighlight>
Output:
Line 1,762 ⟶ 1,955:
=={{header|FreeBASIC}}==
<
Const limite = 100000
Line 1,784 ⟶ 1,977:
Print "Terminos menores que los anteriores: " &cont
End
</syntaxhighlight>
{{out}}
<pre>
Line 1,794 ⟶ 1,987:
=={{header|Fōrmulæ}}==
{{FormulaeEntry|page=https://formulae.org/?script=examples/Hofstadter_Q_sequence}}
'''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,847 ⟶ 2,060:
func showQ(n int) {
fmt.Printf("Q(%d) = %d\n", n, q(n))
}</
{{out}}
<pre>
Line 1,866 ⟶ 2,079:
=={{header|GW-BASIC}}==
<
20 Q(1) = 1: Q(2) = 1
30 FOR N = 3 TO 1000
Line 1,874 ⟶ 2,087:
70 PRINT Q(N)
80 NEXT N
90 PRINT Q(1000)</
=={{header|Haskell}}==
Line 1,880 ⟶ 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,887 ⟶ 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,911 ⟶ 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,920 ⟶ 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,938 ⟶ 2,151:
putStr("1000-th: "); print (q !! 999)
putStr("flips: ")
print $ length $ filter id $ take 100000 (zipWith (>) q (tail q))</
{{out}}
<pre>
Line 1,947 ⟶ 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,967 ⟶ 2,180:
where
qqq :: [Int64]
qqq = map fromIntegral $ take 3000000 q</
=={{header|Icon}} and {{header|Unicon}}==
<
procedure main()
Line 2,008 ⟶ 2,221:
runerr(500,n)
}
end</
{{libheader|Icon Programming Library}}
Line 2,027 ⟶ 2,240:
=={{header|IS-BASIC}}==
<
110 LET LIMIT=1000
120 NUMERIC Q(1 TO LIMIT)
Line 2,038 ⟶ 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 2,048 ⟶ 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 2,068 ⟶ 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 2,113 ⟶ 2,326:
System.out.println("Q(" + maxN + ") was called the most with " + maxUses + " calls");
}
}</
{{out}}
<pre>Q(1) = 1
Line 2,132 ⟶ 2,345:
===ES5===
Based on memoization example from 'JavaScript: The Good Parts'.
<
var memo = [1,1,1];
var Q = function (n) {
Line 2,150 ⟶ 2,363:
console.log('Q(1000) = ' + hofstadterQ(1000));
</syntaxhighlight>
{{out}}
<pre>
Line 2,168 ⟶ 2,381:
===ES6===
Memoising with the accumulator of a fold
<
'use strict';
Line 2,207 ⟶ 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 2,220 ⟶ 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 2,248 ⟶ 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,270 ⟶ 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,287 ⟶ 2,500:
println("First ten elements of sequence: ", join(hofstQseq(1:10), ", "))
println("1000-th element: ", hofstQseq(1000))
</syntaxhighlight>
{{out}}
Line 2,294 ⟶ 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,304 ⟶ 2,517:
=={{header|Kotlin}}==
<
fun main(args: Array<String>) {
Line 2,316 ⟶ 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,327 ⟶ 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,342 ⟶ 2,590:
PRINT FORMAT FMT, 1000, Q(1000)
END OF PROGRAM</
{{out}}
Line 2,362 ⟶ 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,369 ⟶ 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,384 ⟶ 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,400 ⟶ 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,426 ⟶ 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,439 ⟶ 2,687:
<pre>>> sum(diff(Qsequence(100000))<0)
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}}==
<
FROM InOut IMPORT WriteString, WriteCard, WriteLn;
Line 2,464 ⟶ 2,733:
WriteCard(Q[1000],4);
WriteLn();
END QSequence.</
{{out}}
<pre>The first 10 terms are: 1 1 2 3 3 4 5 5 6 6
Line 2,470 ⟶ 2,739:
=={{header|MiniScript}}==
<
Q = function(n)
Line 2,483 ⟶ 2,752:
print "Q(" + i + ") = " + Q(i)
end for
print "Q(1000) = " + Q(1000)</
{{out}}
<pre>Q(1) = 1
Line 2,496 ⟶ 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,511 ⟶ 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,519 ⟶ 2,808:
=={{header|Oberon-2}}==
Works with oo2c version 2
<
MODULE Hofstadter;
IMPORT
Line 2,556 ⟶ 2,845:
Out.String("terms less than the previous: ");Out.LongInt(count,4);Out.Ln
END Hofstadter.
</syntaxhighlight>
Output:
<pre>
Line 2,573 ⟶ 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,582 ⟶ 2,894:
q at(i) q at(i 1-) < ifTrue: [ 1+ ]
]
q left(10) println q at(1000) println println ; </
{{out}}
Line 2,593 ⟶ 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,603 ⟶ 2,915:
=={{header|Pascal}}==
<
const
Line 2,626 ⟶ 2,938:
inc(flips);
writeln('Flips: ', flips);
end.</
{{out}}
<pre>:> ./HofstadterQSequence
Line 2,636 ⟶ 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,647 ⟶ 2,959:
A more verbose and less idiomatic solution:
<
use warnings;
use strict;
Line 2,668 ⟶ 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,688 ⟶ 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,723 ⟶ 3,035:
}
print "Extra credit: $count\n";
</syntaxhighlight>
{{out}}
<pre>
Line 2,734 ⟶ 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).
<!--<
<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,760 ⟶ 3,072:
<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>
<!--</
{{out}}
<pre>
Line 2,770 ⟶ 3,082:
</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,778 ⟶ 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,788 ⟶ 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,812 ⟶ 3,142:
end;
end H;
</syntaxhighlight>
{{out}}
<pre>
Line 2,844 ⟶ 3,174:
</pre>
Bonus to produce the count of unordered values:
<syntaxhighlight lang="text">
declare tally fixed binary (31) initial (0);
Line 2,851 ⟶ 3,181:
end;
put skip data (tally);
</syntaxhighlight>
{{out}}
<pre>
Line 2,859 ⟶ 3,189:
=={{header|PL/M}}==
<
BDOS: PROCEDURE (FN, ARG); DECLARE FN BYTE, ARG ADDRESS; GO TO 5; END BDOS;
EXIT: PROCEDURE; CALL BDOS(0,0); END EXIT;
Line 2,893 ⟶ 3,223:
CALL PRINT$NUMBER(Q(1000));
CALL EXIT;
EOF</
{{out}}
<pre>THE FIRST 10 TERMS ARE: 1 1 2 3 3 4 5 5 6 6
Line 2,899 ⟶ 3,229:
=={{header|PureBasic}}==
<
End 1
EndIf
Line 2,920 ⟶ 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,927 ⟶ 3,257:
=={{header|Python}}==
<
if n < 1 or type(n) != int: raise ValueError("n must be an int >= 1")
try:
Line 2,942 ⟶ 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,950 ⟶ 3,280:
The following code is to be concatenated to the code above:
<
def q1(n):
Line 2,968 ⟶ 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,976 ⟶ 3,306:
===Alternative===
<
l = len(q.seq)
while l <= n:
Line 2,988 ⟶ 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}}==
<
not if
[ drop size 1+ number$
Line 3,023 ⟶ 3,353:
say " decreasing terms" ]
bailed if
[ message take cr echo$ cr ]</
{{out}}
Line 3,031 ⟶ 3,361:
=={{header|R}}==
<
cache <- vector("integer", 0)
cache[1] <- 1
Line 3,059 ⟶ 3,389:
}
cat(count,"terms is less than its preceding term\n")
</syntaxhighlight>
{{out}}
<pre>
Line 3,068 ⟶ 3,398:
=={{header|Racket}}==
<
#lang racket
Line 3,085 ⟶ 3,415:
;; extra credit
(for/sum ([i 100000]) (if (< (Q (add1 i)) (Q i)) 1 0))
</syntaxhighlight>
{{out}}
Line 3,101 ⟶ 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 3,119 ⟶ 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 3,128 ⟶ 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 3,139 ⟶ 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 3,145 ⟶ 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 3,178 ⟶ 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 3,202 ⟶ 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 3,233 ⟶ 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 3,239 ⟶ 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 3,273 ⟶ 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 3,279 ⟶ 3,609:
=={{header|Ring}}==
<
n = 20
aList = list(n)
Line 3,288 ⟶ 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 3,312 ⟶ 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 3,319 ⟶ 3,689:
=={{header|Run BASIC}}==
<
dim Q(n)
Q(1) = 1
Line 3,329 ⟶ 3,699:
if i > 20 then print "n=";using("####",i);using("####",Q(i))
end
</syntaxhighlight>
{{out}}
<pre>
Line 3,360 ⟶ 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,386 ⟶ 3,756:
println!("Term is less than preceding term {} times", nless);
}
</syntaxhighlight>
{{out}}
<pre>
Line 3,408 ⟶ 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,415 ⟶ 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,422 ⟶ 3,792:
Thus we are forced to use a caching featured version.
<
val HofQ = scala.collection.mutable.Map((1->1),(2->1))
Line 3,440 ⟶ 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,459 ⟶ 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,505 ⟶ 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,512 ⟶ 3,882:
=={{header|Seed7}}==
<
const type: intHash is hash [integer] integer;
Line 3,549 ⟶ 3,919:
end for;
writeln("q(n) < q(n-1) for n = 2 .. 100000: " <& less_than_preceding);
end func;</
{{out}}
Line 3,558 ⟶ 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,568 ⟶ 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,588 ⟶ 3,974:
=={{header|Swift}}==
{{trans|C}}
<
var q = Array(repeating: 0, count: n)
Line 3,607 ⟶ 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,617 ⟶ 4,003:
=={{header|Tailspin}}==
<
templates q
def outputFrom: $(1);
Line 3,646 ⟶ 4,032:
[[1, 100000] -> q] -> countDownSteps -> 'Less than previous $; times' -> !OUT::write
</syntaxhighlight>
{{out}}
<pre>
Line 3,655 ⟶ 4,041:
=={{header|Tcl}}==
<
# Index 0 is not used, but putting it in makes the code a bit shorter
Line 3,678 ⟶ 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,698 ⟶ 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,718 ⟶ 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,726 ⟶ 4,112:
=={{header|VBA}}==
<
Public Sub HofstadterQ()
Dim n As Long, smaller As Long
Line 3,742 ⟶ 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,749 ⟶ 4,135:
=={{header|VBScript}}==
<syntaxhighlight lang="vb">
Sub q_sequence(n)
Dim Q()
Line 3,777 ⟶ 4,163:
q_sequence(100000)
</syntaxhighlight>
{{Out}}
Line 3,787 ⟶ 4,173:
=={{header|Visual FoxPro}}==
<
LOCAL p As Integer, i As Integer
CLEAR
Line 3,816 ⟶ 4,202:
RETURN aq[n]
ENDFUNC
</syntaxhighlight>
{{out}}
<pre>
Line 3,827 ⟶ 4,213:
=={{header|Wren}}==
<
var q = List.filled(N + 1, 0)
q[1] = 1
Line 3,840 ⟶ 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,853 ⟶ 4,239:
=={{header|XPL0}}==
<
int N, C, Q(100_001);
[Q(1):= 1; Q(2):= 1; C:= 0;
Line 3,865 ⟶ 4,251:
IntOut(0, Q(1000)); CrLf(0);
IntOut(0, C); CrLf(0);
]</
{{out}}
Line 3,876 ⟶ 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,887 ⟶ 4,273:
flip := 0;
foreach i in (n){ flip += (q[i] > q[i + 1]) }
println("flips: ",flip);</
{{out}}
<pre>
Line 3,898 ⟶ 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,915 ⟶ 4,301:
1090 NEXT j
1100 LET s=q(i)
1110 RETURN</
|