Hofstadter-Conway $10,000 sequence: Difference between revisions
Hofstadter-Conway $10,000 sequence (view source)
Revision as of 18:51, 16 January 2024
, 4 months agoAdded Easylang
m (Hofstadter-Conway $10,000 sequence. Bundled BASIC languages.) |
(Added Easylang) |
||
| (7 intermediate revisions by 6 users not shown) | |||
Line 48:
{{trans|Nim}}
<
V a_list = [0] * (last+1)
a_list[0] = -50'000
Line 67:
amax = 0
lg2++
k1 = n</
{{out}}
Line 87:
<br>The program addresses the problem for l=2**12 (4K). For l=2**20 (1M) you must
allocate dynamic storage instead using static storage.
<
HOFSTADT START
B 72(R15) skip savearea
Line 171:
A DS 4096F array a(uprdim)
REGEQU
END HOFSTADT</
{{out}}
<pre>
Line 189:
=={{header|Ada}}==
<
-- Allocation of arrays on the heap
Line 262:
end Conway;
</syntaxhighlight>
Sample output:
<pre>
Line 293:
{{works with|ALGOL 68G|Any - tested with release [http://sourceforge.net/projects/algol68/files/algol68g/algol68g-2.3.6/algol68g-2.3.6.tar.gz/download algol68g-2.3.6]}}
{{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] - ELLA Algol68 has no printf}}
<
BEGIN
[max]INT a list;
Line 328:
of the same name inside PROC do sqnc - they are in different scopes#
printf(($"You too might have won $1000 with an answer of n = "g(0)$, mallows number))</
Output:
<pre>
Line 356:
Like the other solutions here, this takes the linguistically confusing expression ''"the first position, p in the sequence where │a(n)/n│ < 0.55 for all n > p"'' to mean the last position where the result's ''not'' < 0.55.
<
script o
property lst : {1, 1}
Line 386:
end HC10000
HC10000(2 ^ 20)</
{{output}}
<
=={{header|AutoHotkey}}==
<
CreateLists(2 ** (Max:=20))
Line 439:
n_%A_Index% := a_%A_Index% / A_Index
}
}</
Message box shows:
<pre>Maximum between 2^1 and 2^2 is 0.666667 for n = 3
Line 465:
Iterative approach:
<
BEGIN {
NN = 20;
Line 486:
Q[n] = Q[Q[n-1]]+Q[n-Q[n-1]];
}
} </
Recursive variant:
<
BEGIN {
Q[1] = 1;
Line 529:
S[n] = 1;
return (Q[n]);
} </
Output:
Line 555:
=={{header|BASIC}}==
==={{header|BASIC256}}===
<
pow2 = 2
p2 = 2 ^ pow2
Line 577:
print
print "Mallows number is "; mallows</
{{out}}
<pre>Same as FreeBASIC entry.</pre>
==={{header|BBC BASIC}}===
<
DIM a%(2^20)
a%(1)=1
Line 602:
ENDIF
NEXT n%
PRINT "Mallows number is ";Mallows%</
Results
Line 629:
==={{header|FreeBASIC}}===
{{trans|BBC BASIC}}
<
' compile with: fbc -s console
Line 660:
Print : Print "hit any key to end program"
Sleep
End</
{{out}}
<pre>Maximum between 2 ^ 1 and 2 ^ 2 is 0.66667 at n = 3
Line 684:
Mallows number is 1489</pre>
==={{header|PureBasic}}===
<
Define.i upperlim, i=1, k1=2, n=3, v=1
Define.d Maximum
Line 787 ⟶ 711:
Print(#CRLF$+"Press ENTER to exit."): Input()
CloseConsole()
EndIf</
==={{header|Run BASIC}}===
<
if uprLim < 1 or uprLim > 20 then uprLim = 20
dim a(2^uprLim)
Line 814 ⟶ 738:
end IF
next n
print "Mallows number is ";Mallows</
<pre>Enter upper limit between 1 and 20 (ENTER 20 gives 2^20): ?20
Maximum between 2^1 and 2^2 is 0.666666698 at n = 3
Line 839 ⟶ 763:
==={{header|True BASIC}}===
{{works with|QBasic}}
<
LET p2 = 2^pow2
LET peak = 0.5
Line 865 ⟶ 789:
PRINT
PRINT "Mallows number is "; mallows
END</
{{out}}
<pre>Same as FreeBASIC entry.</pre>
==={{header|Yabasic}}===
<
p2 = 2 ^ pow2
peak = .5
Line 890 ⟶ 814:
next n
print "\nMallows number is ", mallows</
{{out}}
<pre>Same as FreeBASIC entry.</pre>
Line 897 ⟶ 821:
{{trans|BBC_BASIC}}
Nine first results.
<
20 LET a(1)=1: LET a(2)=1
30 LET pow2=2: LET p2=2^pow2
Line 908 ⟶ 832:
100 IF n=p2 THEN PRINT "Maximum (2^";pow2-1;", 2^";pow2;") is ";peak;" at n=";peakpos: LET pow2=pow2+1: LET p2=2^pow2: LET peak=0.5
110 NEXT n
120 PRINT "Mallows number is ";Mallows</
=={{header|Bracmat}}==
<
=
. !arg:(1|2)&1
Line 966 ⟶ 890:
)
)
)</
Output:
<pre>Between 2^0 and 2^1 the maximum value of a(n)/n is reached for n = 1 with the value 1
Line 991 ⟶ 915:
=={{header|C}}==
<
#include <stdlib.h>
Line 1,019 ⟶ 943:
}
return 1;
}</
Results
<pre>Maximum between 2^1 and 2^2 was 0.666667
Line 1,032 ⟶ 956:
{{works with|C#|3.0}}
<
using System;
using System.Linq;
Line 1,076 ⟶ 1,000:
}
}
</syntaxhighlight>
Output:-
<pre>Maximum from 2^1 to 2^2 is 0.666666666666667 at 3
Line 1,101 ⟶ 1,025:
=={{header|C++}}==
<
#include <deque>
#include <iostream>
Line 1,135 ⟶ 1,059:
}
}
</syntaxhighlight>
Output:
<pre>
Line 1,161 ⟶ 1,085:
=={{header|Clojure}}==
<
(:use [clojure.math.numeric-tower :only [expt]]))
Line 1,184 ⟶ 1,108:
(take 4 maxima) "\n"
(apply >= m20) "\n"
(map double m20))) ; output the decimal forms</
=={{header|Common Lisp}}==
<
(make-array '(2) :initial-contents '(1 1) :adjustable t
:element-type 'integer :fill-pointer 2))
Line 1,228 ⟶ 1,152:
(hof-con n)
(do ((i (1- n) (1- i)))
((> (aref *hof-con-ratios* i) 0.55) (+ i 1)))))</
Sample session:
<pre>ROSETTA> (maxima 20)
Line 1,255 ⟶ 1,179:
=={{header|D}}==
<
void hofstadterConwaySequence(in int m) {
Line 1,278 ⟶ 1,202:
void main() {
hofstadterConwaySequence(2 ^^ 20);
}</
Output:
Line 1,300 ⟶ 1,224:
Max in [2^18, 2^19]: 0.534645
Max in [2^19, 2^20]: 0.533779</pre>
=={{header|EasyLang}}==
{{trans|Go}}
<syntaxhighlight>
numfmt 4 0
a[] = [ 1 1 ]
x = 1
n = 2
mallow = 0
for p = 1 to 19
max = 0
nextPot = n * 2
while n < nextPot
n = len a[] + 1
x = a[x] + a[n - x]
a[] &= x
f = x / n
max = higher max f
if f >= 0.55
mallow = n
.
.
print "max between 2^" & p & " and 2^" & p + 1 & " was " & max
.
print "winning number " & mallow
</syntaxhighlight>
=={{header|EchoLisp}}==
<
(decimals 4)
(cache-size 2000000)
Line 1,331 ⟶ 1,281:
#:break (> (// (a n) n) 0.55) => n )
)
</syntaxhighlight>
{{out}}
<pre>
Line 1,359 ⟶ 1,309:
=={{header|Eiffel}}==
<syntaxhighlight lang="eiffel">
class
APPLICATION
Line 1,420 ⟶ 1,370:
end
</syntaxhighlight>
{{out}}
As the run time is quite slow, the test output is shown only up to 2^15.
Line 1,441 ⟶ 1,391:
=={{header|Erlang}}==
<syntaxhighlight lang="erlang">
-module( hofstadter_conway ).
Line 1,477 ⟶ 1,427:
At_end = dict:fetch( Key - Last_number, Dict ),
dict:store( Key, At_begining + At_end, Dict ).
</syntaxhighlight>
{{out}}
<pre>
Line 1,504 ⟶ 1,454:
=={{header|Euler Math Toolbox}}==
<syntaxhighlight lang="euler math toolbox">
>function hofstadter (n) ...
$v=ones(1,n);
Line 1,532 ⟶ 1,482:
>max(nonzeros(v1>0.55))
1489
</syntaxhighlight>
=={{header|F Sharp|F#}}==
<
while a.Count <= (1 <<< 20) do
a.[a.[a.Count - 1]] + a.[a.Count - a.[a.Count - 1]] |> a.Add
Line 1,546 ⟶ 1,496:
|> List.rev
|> List.find (fun (i, n) -> float(n) / float(i) > 0.55)
printfn "Mallows number is %d" mallows</
Outputs:
<pre>Maximum in 2.. 4 is 0.666667
Line 1,570 ⟶ 1,520:
=={{header|Factor}}==
<
prettyprint sequences splitting ;
Line 1,588 ⟶ 1,538:
]
[ "Mallow's number: " write [ 0.55 >= ] find-last drop 1 + . ]
bi</
{{out}}
<pre>
Line 1,614 ⟶ 1,564:
=={{header|Fortran}}==
<syntaxhighlight lang="fortran">
program conway
implicit none
Line 1,660 ⟶ 1,610:
end program conway
</syntaxhighlight>
Output:
Line 1,688 ⟶ 1,638:
=={{header|Fōrmulæ}}==
{{FormulaeEntry|page=https://formulae.org/?script=examples/Hofstadter-Conway_%2410%2C000_sequence}}
'''Solution'''
This is the function according to the definition. It is very inefficient:
[[File:Fōrmulæ - Hofstadter–Conway $10,000 sequence 01.png]]
If a sequence is desired, it is much better to store the already calculated terms:
[[File:Fōrmulæ - Hofstadter–Conway $10,000 sequence 02.png]]
[[File:Fōrmulæ - Hofstadter–Conway $10,000 sequence 03.png]]
[[File:Fōrmulæ - Hofstadter–Conway $10,000 sequence 04.png]]
'''Test case 1.''' Show the maxima of <math>\frac{A(n)}{n}</math> between successive powers of two up to 2<sup>20</sup>
[[File:Fōrmulæ - Hofstadter–Conway $10,000 sequence 05.png]]
[[File:Fōrmulæ - Hofstadter–Conway $10,000 sequence 06.png]]
'''Test case 2.''' compute the value of n that would have won the prize and confirm it is true for n up to 2<sup>20</sup>
[[File:Fōrmulæ - Hofstadter–Conway $10,000 sequence 07.png]]
[[File:Fōrmulæ - Hofstadter–Conway $10,000 sequence 08.png]]
=={{header|FutureBasic}}==
<syntaxhighlight lang="futurebasic">window 1
// Set width of tab
def tab 9
dim as long Mallows, n, pow2, p2, pPos, uprLim
dim as double p
print
// Adjust array elements depending on size of sequence
_maxArrayElements = 1200000
input "Enter upper limit between 1 and 20 (Enter 20 gives 2^20): "; uprLim
dim as double r
dim as long a( _maxArrayElements )
if uprLim < 1 or uprLim > 20 then uprLim = 20
a(1) = 1
a(2) = 1
pow2 = 2
p2 = 2 ^ pow2
p = 0.5
pPos = 0
print
for n = 3 to 2 ^ uprLim
a(n) = a( a( n-1 ) ) + a( n-a( n-1 ) )
r = a(n) / n
if r >= 0.55 then Mallows = n
if r > p
p = r
pPos = n
end if
if n == p2
print "Maximum of a(n)/n between", " 2^"; pow2-1; " and 2^"; pow2," is "; p;, " at n = "; pPos
pow2 = pow2 + 1
p2 = 2 ^ pow2
p = 0.5
end if
next
print
print "Dr. Mallow's winning number is:"; Mallows
HandleEvents</syntaxhighlight>
Output:
<pre>
Enter upper limit between 1 and 20 (Enter 20 gives 2^20): 20
Maximum of a(n)/n between 2^ 1 and 2^ 2 is 0.6666666667 at n = 3
Maximum of a(n)/n between 2^ 2 and 2^ 3 is 0.6666666667 at n = 6
Maximum of a(n)/n between 2^ 3 and 2^ 4 is 0.6363636364 at n = 11
Maximum of a(n)/n between 2^ 4 and 2^ 5 is 0.6086956522 at n = 23
Maximum of a(n)/n between 2^ 5 and 2^ 6 is 0.5909090909 at n = 44
Maximum of a(n)/n between 2^ 6 and 2^ 7 is 0.5760869565 at n = 92
Maximum of a(n)/n between 2^ 7 and 2^ 8 is 0.5674157303 at n = 178
Maximum of a(n)/n between 2^ 8 and 2^ 9 is 0.5594594595 at n = 370
Maximum of a(n)/n between 2^ 9 and 2^ 10 is 0.5549374131 at n = 719
Maximum of a(n)/n between 2^ 10 and 2^ 11 is 0.5501008742 at n = 1487
Maximum of a(n)/n between 2^ 11 and 2^ 12 is 0.5474628926 at n = 2897
Maximum of a(n)/n between 2^ 12 and 2^ 13 is 0.5441447479 at n = 5969
Maximum of a(n)/n between 2^ 13 and 2^ 14 is 0.5424427088 at n = 11651
Maximum of a(n)/n between 2^ 14 and 2^ 15 is 0.5400710975 at n = 22223
Maximum of a(n)/n between 2^ 15 and 2^ 16 is 0.5387840206 at n = 45083
Maximum of a(n)/n between 2^ 16 and 2^ 17 is 0.537043657 at n = 89516
Maximum of a(n)/n between 2^ 17 and 2^ 18 is 0.5360200678 at n = 181385
Maximum of a(n)/n between 2^ 18 and 2^ 19 is 0.5346454311 at n = 353683
Maximum of a(n)/n between 2^ 19 and 2^ 20 is 0.53377923 at n = 722589
Dr. Mallow's winning number is: 1489
</pre>
=={{header|Go}}==
<
import (
Line 1,723 ⟶ 1,772:
}
fmt.Println("winning number", mallow)
}</
Output:
<pre>
Line 1,750 ⟶ 1,799:
=={{header|Haskell}}==
<
import Data.Ord
import Data.Array
Line 1,774 ⟶ 1,823:
max seq = maximumBy (comparing snd) $ zip seq (map hc' seq)
powers = map (\n -> [2^n .. 2^(n + 1) - 1]) [0 .. 19]
mallows = last.takeWhile ((< 0.55) . hc') $ [2^20, 2^20 - 1 .. 1]</
=={{header|Icon}} and {{header|Unicon}}==
<
m := integer(!args) | 20
nextNum := create put(A := [], 1 | 1 | |A[A[*A]]+A[-A[*A]])[*A]
Line 1,792 ⟶ 1,841:
}
write("Mallows's number is ",\mallows | "NOT found!")
end</
Output:
Line 1,820 ⟶ 1,869:
=={{header|J}}==
'''Solution''' (tacit): <
AnN =: % 1+i.@:# NB. a(n)/n
MxAnN =: >./;.1~ 2 (=<.)@:^. 1+i.@# NB. Maxima of a(n)/n between successive powers of 2</
'''Alternative solution''' (exponential growth):
<br>The first, naive, formulation of <code>hc10k</code> grows by a single term every iteration; in this one, the series grows exponentially in the iterations.
<
expand =: 2+I.@;
tail =: copies&.>^:(<@>:`(<@,@2:))
copies =: >: |.@(#!.1 |.)~ 1 j. #;.1 #^:_1 ::1:~ ]~:{.</
'''Example''': <
1 1 2 2 3 4 4 4 5 6 7 7 8 8 8 8 9 ...
AnN A
Line 1,837 ⟶ 1,886:
1 0.666667 0.666667 0.636364 ...
MxAnN@AnN@hc10kE 20
1 0.666667 0.666667 0.636364 ...</
=={{header|Java}}==
Line 1,843 ⟶ 1,892:
Remove translation and provide native Java implementation.
<
// Title: Hofstadter-Conway $10,000 sequence
Line 1,882 ⟶ 1,931:
}
</syntaxhighlight>
{{out}}
<pre>
Line 1,908 ⟶ 1,957:
=={{header|JavaScript}}==
<
var memo = [1, 1];
Line 1,932 ⟶ 1,981:
for(var i = 1; i <= 20; i += 1) {
console.log("Maxima between 2^"+i+"-2^"+(i+1)+" is: "+maxima_between_twos(i)+"\n");
}</
Output:
<pre>Maxima between 2^1-2^2 is: 0.6666666666666666
Line 1,947 ⟶ 1,996:
=={{header|jq}}==
{{works with|jq}}
<
reduce range(3; $limit) as $n ([0,1,1];
.[$n-1] as $p
Line 1,972 ⟶ 2,021:
| "\nMallows' number = \(.)") ;
task( pow(2;20) + 1 )</
{{out}}
<pre>
Line 2,002 ⟶ 2,051:
=={{header|Julia}}==
<
# Task 1
Line 2,039 ⟶ 2,088:
end
println("You too might have won \$1000 with the mallows number of ", lastindex(0.55))</
{{out}}
Line 2,065 ⟶ 2,114:
=={{header|Kotlin}}==
<
fun main(args: Array<String>) {
Line 2,101 ⟶ 2,150:
}
println("\nMallows' number = $prize")
}</
{{out}}
Line 2,133 ⟶ 2,182:
=={{header|Lua}}==
I solved it, using a coroutine to generate the Hofstadter numbers, because it's fun to do so. This can be done differently, but not with so much fun, I guess. It's counting from the first number 1, the second 1, the third 2 and so on. This doesn't change anything about the outcome, but I guess it's better like this and consistent with such things like fibonacci numbers.
<
local fmt, write=string.format,io.write
local hof=coroutine.wrap(function()
Line 2,170 ⟶ 2,219:
end
write("So Mallows number is ", mallows, " with ", fmt("%.4f",mdiv), ", yay, just wire me my $10000 now!\n")
</syntaxhighlight>
{{out}}
<pre>
Line 2,197 ⟶ 2,246:
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<
a[n_] := a[n] = a[a[n-1]] + a[n-a[n-1]]
Map[Print["Max value: ",Max[Table[a[n]/n//N,{n,2^#,2^(#+1)}]]," for n between 2^",#," and 2^",(#+1)]& , Range[19]]
n=2^20; While[(a[n]/n//N)<0.55,n--]; Print["Mallows number: ",n]</
Outputs:
Line 2,227 ⟶ 2,276:
=={{header|MATLAB}} / {{header|Octave}}==
<
Q = zeros(1,N);
Q(1:2) = 1;
Line 2,233 ⟶ 2,282:
Q(n) = Q(Q(n-1))+Q(n-Q(n-1));
end;
end;</
The function can be tested in this way:
<
Q = HCsequence(2^NN+1);
V = Q./(1:2^NN);
Line 2,243 ⟶ 2,292:
i = i + 2^k - 1;
printf('Maximum between 2^%i and 2^%i is %f at n=%i\n',k,k+1,m,i);
end; </
Output:
Line 2,268 ⟶ 2,317:
=={{header|Nim}}==
{{trans|C}}
<
const last = 1 shl 20
Line 2,288 ⟶ 2,337:
aMax = 0
inc lg2
k1 = n</
Output:
<pre>Maximum between 2^1 and 2^2 was 0.6666666666666666
Line 2,299 ⟶ 2,348:
=={{header|Objeck}}==
<
class HofCon {
function : Main(args : String[]) ~ Nil {
Line 2,338 ⟶ 2,387:
}
}
</syntaxhighlight>
<pre>
Line 2,364 ⟶ 2,413:
=={{header|Oforth}}==
<
| l i |
ListBuffer newSize(n) dup add(1) dup add(1) ->l
Line 2,381 ⟶ 2,430:
"Mallows number ==>" . h reverse detect(#[ first 0.55 >= ], true) println
; </
{{out}}
Line 2,409 ⟶ 2,458:
=={{header|Oz}}==
A direct implementation of the recursive definition with explicit memoization using a mutable map (dictionary):
<
local
Cache = {Dictionary.new}
Line 2,435 ⟶ 2,484:
in
{System.showInfo "Max. between 2^"#I#" and 2^"#I+1#": "#Maximum}
end</
Output:
Line 2,462 ⟶ 2,511:
=={{header|PARI/GP}}==
<
maxima(n)=my(a=HC(1<<n),m);vector(n-1,k,m=0;for(i=1<<k+1,1<<(k+1)-1,m=max(m,a[i]/i));m);
forstep(i=#a,1,-1,if(a[i]/i>=.55,return(i)))</
Output:
<pre>%1 = [2/3, 2/3, 7/11, 14/23, 13/22, 53/92, 101/178, 207/370, 399/719, 818/1487, 1586/2897, 3248/5969, 6320/11651, 12002/22223, 24290/45083, 24037/44758, 97226/181385, 189095/353683, 385703/722589]
Line 2,471 ⟶ 2,520:
=={{header|Pascal}}==
tested with freepascal 3.1.1 64 Bit.
<
program HofStadterConway;
const
Line 2,591 ⟶ 2,640:
writeln('Mallows number with limit ',l:10:8,' at ',SearchLastPos(a,l));
freemem(p);
end.</
;output:
<pre>
Line 2,610 ⟶ 2,659:
=={{header|Perl}}==
<
use warnings ;
use strict ;
Line 2,635 ⟶ 2,684:
}
print "The prize would have been won at $mallows !\n"
</syntaxhighlight>
Output:
<pre>Between 2 ^ 1 and 2 ^ 2 the maximum value is 0.666666666666667 at 3 !
Line 2,660 ⟶ 2,709:
=={{header|Phix}}==
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">a</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,688 ⟶ 2,737:
<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;">"Mallows number is %d\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">mallows</span><span style="color: #0000FF;">})</span>
<!--</
In this particular case the for loop of q() only ever iterates 0 or 1 times.
{{out}}
Line 2,716 ⟶ 2,765:
=={{header|Picat}}==
<
foreach(N in 0..19)
[Val,Ix] = argmax({a(I)/I : I in 2**N..2**(N+1)}),
Line 2,753 ⟶ 2,802:
end
end
end.</
{{out}}
Line 2,779 ⟶ 2,828:
=={{header|PicoLisp}}==
<
(cache '(NIL) N
(if (>= 2 N)
Line 2,807 ⟶ 2,856:
" (the task requests 'n > p' now)" ) ) )
(sequence (** 2 20))</
Output:
<pre>Maximum between 2 and 4 was 0.66666666666666666667
Line 2,831 ⟶ 2,880:
=={{header|PL/I}}==
<syntaxhighlight lang="pl/i">
/* First part: */
Line 2,840 ⟶ 2,889:
L(i) = L(i-k) + L(1+k);
end;
</syntaxhighlight>
=={{header|Python}}==
<
def maxandmallows(nmaxpower2):
Line 2,875 ⟶ 2,924:
if mallows:
print("\nYou too might have won $1000 with the mallows number of %i" % mallows)
</syntaxhighlight>
''Sample output''
Line 2,904 ⟶ 2,953:
=={{header|Quackery}}==
<
[ ' [ 1 1 ]
Line 2,929 ⟶ 2,978:
dup echo
say " is " 10 point$ echo$ cr ]
drop</
{{out}}
Line 2,958 ⟶ 3,007:
A memoizing function to compute individual elements of the sequence could be written like this:
<
{a = c(1, 1)
function(n)
{if (is.na(a[n]))
a[n] <<- f(f(n - 1)) + f(n - f(n - 1))
a[n]}})</
But a more straightforward way to get the local maxima and the Mallows point is to begin by generating as much of the sequence as we need.
<
for (n in 3 : (2^20))
{hofcon[n] =
hofcon[hofcon[n - 1]] +
hofcon[n - hofcon[n - 1]]}</
We can now quickly finish the task with vectorized operations.
<
message("Maxima:")
Line 2,982 ⟶ 3,031:
message("Prize-winning point:")
print(max(which(ratios >= .55)))</
{{out}}
<pre>
Line 2,998 ⟶ 3,047:
The macro define/memoize1 creates an 1-argument procedure and handles all the details about memorization. We use it to define (conway n) as a transcription of the definition.
<
(define-syntax-rule (define/memoize1 (proc x) body ...)
Line 3,011 ⟶ 3,060:
1
(+ (conway (conway (sub1 n)))
(conway (- n (conway (sub1 n)))))))</
The macro for/max1 is like for, but the result is the maximum of the values produced by the body. The result also includes the position of the maximum in the sequence. We use this to find the maximum in each power-of-2-sector.
<
(for/fold ([max -inf.0] [arg-max #f]) ([i sequence])
(define val (begin body ...))
Line 3,026 ⟶ 3,075:
(define-values (max arg-max) (for/max1 ([k (in-range low-b up-b)])
(/ (conway k) k)))
(printf "Max. between 2^~a and 2^~a is ~a at ~a ~n" i (add1 i) (real->decimal-string max 5) arg-max))</
The macro for/prev is like for/and, it stops when it finds the first #f, but the result is previous value produced by the body. We use this to find the first power-of-2-sector that has no ratio avobe .55. The previous result is the Mallows number.
<
(for/fold ([prev #f]) (sequences ...)
(define val (let () body ...))
Line 3,043 ⟶ 3,092:
k)))
(printf "Mallows number: ~a~n" mallows)</
'''Sample Output:'''
Line 3,072 ⟶ 3,121:
{{works with|Rakudo|2018.09}}
Note that <tt>@a</tt> is a lazy array, and the Z variants are "zipwith" operators.
<syntaxhighlight lang="raku"
my @a = (0,1,1, -> $p { @a[$p] + @a[$n++ - $p] } ... *);
@a[2**20]; # pre-calculate sequence
Line 3,085 ⟶ 3,134:
$max.key, ' at ', $max.value;
}
say "Mallows' number would appear to be ", $last55;</
{{out}}
<pre> 1 2..3 0.666666666666667 at 3
Line 3,109 ⟶ 3,158:
=={{header|REXX}}==
<
@pref= 'Maximum of a(n) ÷ n between ' /*a prologue for the text of message. */
H.=.; H.1=1; H.2=1; !.=0; @.=0 /*initialize some REXX variables. */
Line 3,131 ⟶ 3,180:
H: procedure expose H.; parse arg z
if H.z==. then do; m=z-1; $=H.m; _=z-$; H.z=H.$+H._; end
return H.z</
'''output'''
<pre>
Line 3,159 ⟶ 3,208:
=={{header|Ring}}==
<
decimals(9)
size = 15
Line 3,181 ⟶ 3,230:
next
see "mallows number is : " + mallows + nl
</syntaxhighlight>
Output:
<pre>
Line 3,202 ⟶ 3,251:
=={{header|Ruby}}==
<
def initialize
@sequence = [nil, 1, 1]
Line 3,230 ⟶ 3,279:
end
puts "the mallows number is #{mallows}"</
{{out}}
Line 3,257 ⟶ 3,306:
=={{header|Rust}}==
<
struct HofstadterConway {
current: usize,
Line 3,317 ⟶ 3,366:
println!("Winning number: {}", winning_num);
}
</syntaxhighlight>
{{out}}
<pre>
Line 3,345 ⟶ 3,394:
=={{header|Scala}}==
<
def pow2(n: Int): Int = (Iterator.fill(n)(2)).product
Line 3,373 ⟶ 3,422:
println("Mallow's number = %s".format(mallowsNumber))
}
}</
'''Output'''
<pre>Maximum of a(n)/n between 2^1 and 2^2 was 0.6666666666666666 at 3
Line 3,398 ⟶ 3,447:
=={{header|Scheme}}==
<
(import (scheme base)
(scheme write)
Line 3,442 ⟶ 3,491:
0.55))
(display (string-append "\np=" (number->string idx) "\n"))))
</syntaxhighlight>
{{out}}
Line 3,471 ⟶ 3,520:
=={{header|Sidef}}==
{{trans|Ruby}}
<
has sequence = [nil, 1, 1]
method term(n {.is_pos}) {
Line 3,494 ⟶ 3,543:
}
say "the mallows number is #{mallows}"</
{{out}}
<pre>
Line 3,521 ⟶ 3,570:
=={{header|Swift}}==
{{trans|Java}}
<
var aList = [Int](count: m + 1, repeatedValue: 0)
var k1 = 2
Line 3,549 ⟶ 3,598:
}
doSqnc(1 << 20)</
{{out}}
<pre>
Line 3,575 ⟶ 3,624:
=={{header|Tcl}}==
The routine to return the ''n''<sup>th</sup> member of the sequence.
<
set hofcon10k {1 1}
Line 3,592 ⟶ 3,641:
}
return $c
}</
The code to explore the sequence, looking for maxima in the ratio.
<
set end [expr {2**($p+1)}]
set maxI 0; set maxV 0
Line 3,602 ⟶ 3,651:
}
puts "max in 2**$p..2**[expr {$p+1}] at $maxI : $maxV"
}</
Output:
<pre>
Line 3,628 ⟶ 3,677:
=={{header|VBA}}==
{{trans|Phix}} Function q rewritten to sub.
<
Sub make_q()
ReDim q(2 ^ 20)
Line 3,661 ⟶ 3,710:
Next p
Debug.Print "Mallows number is"; mallows
End Sub</
<pre>Maximum in range 1 to 2 occurs at 1: 1,000000
Maximum in range 2 to 4 occurs at 3: 0,666667
Line 3,684 ⟶ 3,733:
Mallows number is 1489 </pre>
=={{header|V (Vlang)}}==
{{trans|go}}
<syntaxhighlight lang="v (vlang)">fn main() {
mut a := [0, 1, 1] // ignore 0 element. work 1 based.
mut x := 1 // last number in list
Line 3,708 ⟶ 3,757:
}
println("winning number $mallow")
}</
{{out}}
<pre>
Line 3,736 ⟶ 3,785:
{{trans|Kotlin}}
{{libheader|Wren-fmt}}
<
var limit = 1<<20 + 1
Line 3,770 ⟶ 3,819:
}
}
System.print("\nMallows' number = %(prize)")</
{{out}}
Line 3,802 ⟶ 3,851:
=={{header|X86 Assembly}}==
Using FASM syntax.
<
call a.memorization
call Mallows_Number
Line 3,837 ⟶ 3,886:
retn
a rd 1 shl 20</
=={{header|XPL0}}==
<syntaxhighlight lang "XPL0">int A(1 + 1<<20), N, Power2, WinningN;
real Max, Member;
[A(1):= 1; A(2):= 1;
N:= 3; Power2:= 2; Max:= 0.;
Text(0, " Range Maximum^m^j");
Format(1, 6);
repeat A(N):= A(A(N-1)) + A(N-A(N-1));
Member:= float(A(N)) / float(N);
if Member >= Max then Max:= Member;
if Member >= 0.55 then WinningN:= N;
if N & 1<<Power2 then
[Text(0, "2^^"); IntOut(0, Power2-1);
Text(0, " to 2^^"); IntOut(0, Power2);
ChOut(0, 9\tab\);
RlOut(0, Max);
CrLf(0);
Power2:= Power2+1;
Max:= 0.;
];
N:= N+1;
until N > 1<<20;
IntOut(0, WinningN);
Text(0, " is the winning position.^m^j");
]</syntaxhighlight>
{{out}}
<pre>
Range Maximum
2^1 to 2^2 0.666667
2^2 to 2^3 0.666667
2^3 to 2^4 0.636364
2^4 to 2^5 0.608696
2^5 to 2^6 0.590909
2^6 to 2^7 0.576087
2^7 to 2^8 0.567416
2^8 to 2^9 0.559459
2^9 to 2^10 0.554937
2^10 to 2^11 0.550101
2^11 to 2^12 0.547463
2^12 to 2^13 0.544145
2^13 to 2^14 0.542443
2^14 to 2^15 0.540071
2^15 to 2^16 0.538784
2^16 to 2^17 0.537044
2^17 to 2^18 0.536020
2^18 to 2^19 0.534645
2^19 to 2^20 0.533779
1489 is the winning position.
</pre>
=={{header|zkl}}==
<
a:=List.createLong(m + 1,0);
a[0]=a[1]=1;
Line 3,859 ⟶ 3,958:
}
hofstadterConwaySequence((2).pow(20));</
{{out}}
<pre>
| |||