Hofstadter-Conway $10,000 sequence: Difference between revisions

It was later found that [[wp:Douglas Hofstadter|Hofstadter]] had also done prior work on the sequence.

 

 

 

*   [http://mathworld.wolfram.com/Hofstadter-Conway10000-DollarSequence.html Mathworld Article].

<br><br>

 

=={{header|360 Assembly}}==

<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

A DS 4096F array a(uprdim)

REGEQU

{{out}}

<pre>

 

=={{header|Ada}}==

-- Allocation of arrays on the heap

 

end Conway;

 

Sample output:

<pre>

{{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;

of the same name inside PROC do sqnc - they are in different scopes#

 

Output:

<pre>

You too might have won $1000 with an answer of n = 1489

</pre>

 

=={{header|AutoHotkey}}==

CreateLists(2 ** (Max:=20))

 

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

 

Iterative approach:

BEGIN {

NN = 20;

Q[n] = Q[Q[n-1]]+Q[n-Q[n-1]];

}

 

Recursive variant:

 

BEGIN {

Q[1] = 1;

S[n] = 1;

return (Q[n]);

 

Output:

</pre>

 

DIM a%(2^20)

a%(1)=1

ENDIF

NEXT n%

 

Results

Maximum between 2^19 and 2^20 is 0.53377923 at n=722589

Mallows number is 1489</pre>

 

=={{header|Bracmat}}==

=

. !arg:(1|2)&1

)

)

Output:

<pre>Between 2^0 and 2^1 the maximum value of a(n)/n is reached for n = 1 with the value 1

 

=={{header|C}}==

#include <stdlib.h>

 

}

return 1;

Results

<pre>Maximum between 2^1 and 2^2 was 0.666667

Maximum between 2^19 and 2^20 was 0.533779</pre>

 

=={{header|C sharp|C#}}==

{{works with|C#|3.0}}

 

using System;

using System.Linq;

}

}

Output:-

<pre>Maximum from 2^1 to 2^2 is 0.666666666666667 at 3

The winning number is 1489.

</pre>

=={{header|Clojure}}==

(:use [clojure.math.numeric-tower :only [expt]]))

 

(take 4 maxima) "\n"

(apply >= m20) "\n"

 

=={{header|Common Lisp}}==

(make-array '(2) :initial-contents '(1 1) :adjustable t

:element-type 'integer :fill-pointer 2))

(hof-con n)

(do ((i (1- n) (1- i)))

Sample session:

<pre>ROSETTA> (maxima 20)

 

=={{header|D}}==

 

void hofstadterConwaySequence(in int m) {

void main() {

hofstadterConwaySequence(2 ^^ 20);

 

Output:

Max in [2^18, 2^19]: 0.534645

Max in [2^19, 2^20]: 0.533779</pre>

 

=={{header|EchoLisp}}==

(decimals 4)

(cache-size 2000000)

#:break (> (// (a n) n) 0.55) => n )

)

{{out}}

<pre>

→ 1489 ;; Mallows number

</pre>

 

=={{header|Eiffel}}==

class

APPLICATION

 

end

{{out}}

As the run time is quite slow, the test output is shown only up to 2^15.

 

=={{header|Erlang}}==

-module( hofstadter_conway ).

 

At_end = dict:fetch( Key - Last_number, Dict ),

dict:store( Key, At_begining + At_end, Dict ).

{{out}}

<pre>

=={{header|Euler Math Toolbox}}==

 

>function hofstadter (n) ...

$v=ones(1,n);

>max(nonzeros(v1>0.55))

1489

=={{header|F Sharp|F#}}==

while a.Count <= (1 <<< 20) do

a.[a.[a.Count - 1]] + a.[a.Count - a.[a.Count - 1]] |> a.Add

|> List.rev

|> List.find (fun (i, n) -> float(n) / float(i) > 0.55)

Outputs:

<pre>Maximum in 2.. 4 is 0.666667

Maximum in 524288..1048576 is 0.533779

Mallows number is 1489</pre>

=={{header|Fortran}}==

program conway

implicit none

 

end program conway

 

Output:

Mallows number = 1489

</pre>

 

 

 

 

 

 

=={{header|FutureBasic}}==

 

// Set width of tab

print

print "Dr. Mallow's winning number is:"; Mallows

 

Output:

 

=={{header|Go}}==

 

import (

}

fmt.Println("winning number", mallow)

Output:

<pre>

 

=={{header|Haskell}}==

import Data.Ord

import Data.Array

max seq = maximumBy (comparing snd) $ zip seq (map hc' seq)

powers = map (\n -> [2^n .. 2^(n + 1) - 1]) [0 .. 19]

 

=={{header|Icon}} and {{header|Unicon}}==

m := integer(!args) | 20

nextNum := create put(A := [], 1 | 1 | |A[A[*A]]+A[-A[*A]])[*A]

}

write("Mallows's number is ",\mallows | "NOT found!")

 

Output:

 

=={{header|J}}==

AnN =: % 1+i.@:# NB. a(n)/n

'''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:))

 

1 1 2 2 3 4 4 4 5 6 7 7 8 8 8 8 9 ...

AnN A

1 0.666667 0.666667 0.636364 ...

MxAnN@AnN@hc10kE 20

=={{header|Java}}==

=={{header|JavaScript}}==

var memo = [1, 1];

 

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

Maxima between 2^19-2^20 is: 0.5337792299633678

Maxima between 2^20-2^21 is: 0.5326770563524978

</pre>

 

=={{header|Julia}}==

 

# Task 1

end

 

 

{{out}}

 

=={{header|Kotlin}}==

 

fun main(args: Array<String>) {

}

println("\nMallows' number = $prize")

 

{{out}}

 

Mallows' number = 1489

</pre>

 

=={{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]]

 

Outputs:

=={{header|MATLAB}} / {{header|Octave}}==

Q = zeros(1,N);

Q(1:2) = 1;

Q(n) = Q(Q(n-1))+Q(n-Q(n-1));

end;

 

The function can be tested in this way:

Q = HCsequence(2^NN+1);

V = Q./(1:2^NN);

i = i + 2^k - 1;

printf('Maximum between 2^%i and 2^%i is %f at n=%i\n',k,k+1,m,i);

 

Output:

=={{header|Nim}}==

{{trans|C}}

 

const last = 1 shl 20

aMax = 0

inc lg2

Output:

<pre>Maximum between 2^1 and 2^2 was 0.6666666666666666

 

=={{header|Objeck}}==

class HofCon {

function : Main(args : String[]) ~ Nil {

}

}

 

<pre>

Maximum between 2^19 and 2^20 was 0.53377923

</pre>

 

=={{header|Oforth}}==

 

| l i |

ListBuffer newSize(n) dup add(1) dup add(1) ->l

"Mallows number ==>" . h reverse detect(#[ first 0.55 >= ], true) println

 

{{out}}

=={{header|Oz}}==

A direct implementation of the recursive definition with explicit memoization using a mutable map (dictionary):

local

Cache = {Dictionary.new}

in

{System.showInfo "Max. between 2^"#I#" and 2^"#I+1#": "#Maximum}

 

Output:

 

=={{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);

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]

%2 = 1489</pre>

=={{header|Pascal}}==

tested with freepascal 3.1.1 64 Bit.

program HofStadterConway;

const

writeln('Mallows number with limit ',l:10:8,' at ',SearchLastPos(a,l));

freemem(p);

;output:

<pre>

 

=={{header|Perl}}==

use warnings ;

use strict ;

}

print "The prize would have been won at $mallows !\n"

Output:

<pre>Between 2 ^ 1 and 2 ^ 2 the maximum value is 0.666666666666667 at 3 !

</pre>

 

{{out}}

 

 

=={{header|PicoLisp}}==

(cache '(NIL) N

(if (>= 2 N)

" (the task requests 'n > p' now)" ) ) )

 

Output:

<pre>Maximum between 2 and 4 was 0.66666666666666666667

 

=={{header|PL/I}}==

/* First part: */

 

L(i) = L(i-k) + L(1+k);

end;

 

=={{header|Python}}==

 

 

def maxandmallows(nmaxpower2):

if mallows:

print("\nYou too might have won $1000 with the mallows number of %i" % mallows)

 

''Sample output''

You too might have won $1000 with the mallows number of 1489</pre>

If you don't create enough terms in the sequence, no mallows number is returned.

 

=={{header|R}}==

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))

 

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]] +

 

We can now quickly finish the task with vectorized operations.

 

 

message("Maxima:")

 

message("Prize-winning point:")

{{out}}

<pre>

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 ...)

1

(+ (conway (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 ...))

(define-values (max arg-max) (for/max1 ([k (in-range low-b up-b)])

(/ (conway k) k)))

 

 

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 ...))

k)))

 

 

'''Sample Output:'''

Max. between 2^19 and 2^20 is 0.53378 at 722589

Mallows number: 1489</pre>

 

=={{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. */

H: procedure expose H.; parse arg z

if H.z==. then do; m=z-1; $=H.m; _=z-$; H.z=H.$+H._; end

'''output'''

<pre>

 

=={{header|Ring}}==

decimals(9)

size = 15

next

see "mallows number is : " + mallows + nl

Output:

<pre>

 

=={{header|Ruby}}==

def initialize

@sequence = [nil, 1, 1]

end

 

 

{{out}}

</pre>

 

 

=={{header|Scala}}==

def pow2(n: Int): Int = (Iterator.fill(n)(2)).product

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

=={{header|Scheme}}==

 

(import (scheme base)

(scheme write)

0.55))

(display (string-append "\np=" (number->string idx) "\n"))))

 

{{out}}

=={{header|Sidef}}==

{{trans|Ruby}}

has sequence = [nil, 1, 1]

method term(n {.is_pos}) {

}

 

{{out}}

<pre>

=={{header|Swift}}==

{{trans|Java}}

var aList = [Int](count: m + 1, repeatedValue: 0)

var k1 = 2

}

 

{{out}}

<pre>

=={{header|Tcl}}==

The routine to return the ''n''^th member of the sequence.

 

set hofcon10k {1 1}

}

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

}

puts "max in 2**$p..2**[expr {$p+1}] at $maxI : $maxV"

Output:

<pre>

max in 2**18..2**19 at 353683 : 0.5346454310781124

max in 2**19..2**20 at 722589 : 0.5337792299633678

</pre>

 

=={{header|X86 Assembly}}==

Using FASM syntax.

call a.memorization

call Mallows_Number

retn

 

 

=={{header|zkl}}==

a:=List.createLong(m + 1,0);

a[0]=a[1]=1;

}

{{out}}

<pre>

Winning number = 1489

</pre>