Source code in the basic programming language

arraybase 1
pow2 = 2
p2 = 2 ^ pow2
peak = .5
dim a(2 ^ 20)
a[1] = 1
a[2] = 1

for n = 3 to 2 ^ 20
    a[n] = a[a[n-1]] + a[n-a[n-1]]
    r = a[n] / n
    if r >= .55 then mallows = n
    if r > peak then peak = r : peakpos = n
    if n = p2 then
        print "Maximum between 2 ^ "; rjust((pow2 - 1),2); " and 2 ^ "; rjust(pow2,2); " is "; ljust(peak,13,"0"); " at n = "; peakpos
        pow2 += 1
        p2 = 2 ^ pow2
        peak = .5
    end if
next n

print
print "Mallows number is "; mallows

HIMEM=LOMEM+1E7 : REM Reserve enough memory for a 4 MB array, plus other code
DIM a%(2^20)
a%(1)=1
a%(2)=1
pow2%=2
p2%=2^pow2%
peak=0.5
peakpos%=0
FOR n%=3 TO 2^20
   a%(n%)=a%(a%(n%-1))+a%(n%-a%(n%-1))
   r=a%(n%)/n%
   IF r>=0.55 THEN Mallows%=n%
   IF r>peak THEN peak=r:peakpos%=n%
   IF n%=p2% THEN
      PRINT "Maximum between 2^";pow2%-1;" and 2^";pow2%;" is ";peak;" at n=";peakpos%
      pow2%+=1
      p2%=2^pow2%
      peak=0.5
   ENDIF
NEXT n%
PRINT "Mallows number is ";Mallows%


' version 13-07-2018
' compile with: fbc -s console

Dim As UInteger a(), pow2 = 2, p2 = 2 ^ pow2, peakpos, n, mallows
Dim As Double peak = 0.5, r
ReDim a(2 ^ 20)
a(1) = 1
a(2) = 1

For n = 3 To 2 ^ 20
    a(n) = a(a(n -1)) + a(n - a(n -1))
    r = a(n) / n
    If r >= 0.55 Then mallows = n
    If r > peak Then peak = r : peakpos = n
    If n = p2 Then
        Print Using "Maximum between 2 ^ ## and 2 ^ ## is"; pow2 -1; pow2;
        Print Using " #.##### at n = "; peak;
        Print peakpos
        pow2 += 1
        p2 = 2 ^ pow2
        peak = 0.5
    End If
Next

Print
Print "Mallows number is "; mallows

' empty keyboard buffer
While Inkey <> "" : Wend
Print : Print "hit any key to end program"
Sleep
End

If OpenConsole()
  Define.i upperlim, i=1, k1=2, n=3, v=1
  Define.d Maximum
  Print("Enter limit (ENTER gives 2^20=1048576): "): upperlim=Val(Input())
  If upperlim<=0: upperlim=1048576: EndIf
  Dim tal(upperlim)
  If ArraySize(tal())=-1
    PrintN("Could not allocate needed memory!"): Input(): End
  EndIf
  tal(1)=1: tal(2)=1
  While n<=upperlim
    v=tal(v)+tal(n-v)
    tal(n)=v
    If Maximum<(v/n): Maximum=v/n: EndIf
    If Not n&k1
      PrintN("Maximum between 2^"+Str(i)+" and 2^"+Str(i+1)+" was "+StrD(Maximum,6))
      Maximum=0.0
      i+1
    EndIf
    k1=n
    n+1
  Wend
  
  Print(#CRLF$+"Press ENTER to exit."): Input()
  CloseConsole()
EndIf

input "Enter upper limit between 1 and 20 (ENTER 20 gives 2^20):"); uprLim
if uprLim < 1 or uprLim > 20 then uprLim = 20
dim a(2^uprLim)
a(1)	= 1
a(2)	= 1
pow2	= 2
p2	= 2^pow2
p	= 0.5
pPos	= 0
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  THEN 
     p    = r
     pPos = n
   end if 
   if n	= p2 THEN
      print "Maximum between";chr$(9);" 2^";pow2-1;" and 2^";pow2;chr$(9);" is ";p;chr$(9);" at n = ";pPos
      pow2 = pow2 + 1
      p2   = 2^pow2
      p	   = 0.5
   end IF
next n
print "Mallows number is ";Mallows

LET pow2 = 2
LET p2 = 2^pow2
LET peak = 0.5
DIM a(0)
MAT REDIM a(2^20)
LET a(1) = 1
LET a(2) = 1
FOR n = 3 TO 2^20
    LET a(n) = a(a(n-1))+a(n-a(n-1))
    LET r = a(n)/n
    IF r >= 0.55 THEN LET mallows = n
    IF r > peak THEN
       LET peak = r
       LET peakpos = n
    END IF
    IF n = p2 THEN
       PRINT USING "Maximum between 2 ^ ## and 2 ^ ## is": pow2-1, pow2;
       PRINT USING " #.##### at n = ": peak;
       PRINT peakpos
       LET pow2 = pow2+1
       LET p2 = 2^pow2
       LET peak = 0.5
    END IF
NEXT n
PRINT
PRINT "Mallows number is "; mallows
END


pow2 = 2
p2 = 2 ^ pow2
peak = .5
dim a(2 ^ 20)
a(1) = 1
a(2) = 1

for n = 3 to 2 ^ 20
    a(n) = a(a(n - 1)) + a(n - a(n - 1))
    r = a(n) / n
    if r >= .55  mallows = n
    if r > peak then peak = r : peakpos = n : fi
    if n = p2 then
       print "Maximum between 2 ^ ", pow2 - 1 using("##"), " and 2 ^ ", pow2 using("##"), " is ", peak using("#.#####"), " at n = ", peakpos
       pow2 = pow2 + 1
       p2 = 2 ^ pow2
       peak = .5
    end if
next n

print "\nMallows number is ", mallows

10 DIM a(2000)
20 LET a(1)=1: LET a(2)=1
30 LET pow2=2: LET p2=2^pow2
40 LET peak=0.5: LET peakpos=0
50 FOR n=3 TO 2000
60 LET a(n)=a(a(n-1))+a(n-a(n-1))
70 LET r=a(n)/n
80 IF r>0.55 THEN LET Mallows=n
90 IF r>peak THEN LET peak=r: LET peakpos=n
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