Hofstadter Q sequence: Difference between revisions
m
→{{header|Wren}}: Changed to Wren S/H
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
m (→{{header|Wren}}: Changed to Wren S/H) |
||
| (13 intermediate revisions by 11 users not shown) | |||
Line 731:
number of Q(n)<Q(n+1) for n<=100000 : 49798</pre>
=={{header|
==={{header|BASIC256}}===
{{trans|FreeBASIC}}
<syntaxhighlight lang="basic256">
Line 757 ⟶ 758:
</pre>
==={{header|BBC BASIC}}===
<syntaxhighlight lang="bbcbasic"> PRINT "First 10 terms of Q = " ;
FOR i% = 1 TO 10 : PRINT ;FNq(i%, c%) " "; : NEXT : PRINT
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}}==
Line 1,395 ⟶ 1,505:
<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}}==
Line 1,612 ⟶ 1,748:
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#}}==
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}}==
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}}==
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>
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}}==
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 |
Line 3,307 ⟶ 3,619:
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}}==
Line 3,576 ⟶ 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}}==
Line 3,593 ⟶ 3,961:
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]}}"</syntaxhighlight>
Line 3,845 ⟶ 4,213:
=={{header|Wren}}==
<syntaxhighlight lang="
var q = List.filled(N + 1, 0)
q[1] = 1
| |||