Problem Statement

The definition of the sequence is colloquially described as: Note that indexing for the description above starts from alternately the left and right ends of the list and starts from an index of one. A less wordy description of the sequence is: The sequence begins: Interesting features of the sequence are that:

The sequence is so named because John Conway offered a prize of $10,000 to the first person who could find the first position,   p   in the sequence where It was later found that Hofstadter had also done prior work on the sequence. The 'prize' was won quite quickly by Dr. Colin L. Mallows who proved the properties of the sequence and allowed him to find the value of   n   (which is much smaller than the 3,173,375,556 quoted in the NYT article).

Let's start with the solution:

; Hofstadter-Conway $10,000 sequence
    call a.memorization
    call Mallows_Number
; ECX is the $1000 #
    int3

a.memorization:
; skip [a] to make it one based
    mov [a+1*4],1
    mov [a+2*4],1
    mov ecx,3
@@:
    mov eax,ecx
    mov edx,[a+(ecx-1)*4] ; a[n-1]
    sub eax,edx           ; n-a[n-1]
    mov eax,[a+eax*4]     ; a[n-a[n-1]]
    add eax,[a+edx*4]     ;+a[a[n-1]]
    mov [a+ecx*4],eax
    inc ecx
    cmp ecx,1 shl 20
    jnz @B
    retn

_0.55 equ ((55 shl 32)/100) ; Floor[55 * 2^N / 100], for N=32

Mallows_Number: ; $5D1
    mov ecx,1 shl 20
@@: dec ecx
    mov edx,[a+ecx*4]
    xor eax,eax
    div ecx
    cmp eax,_0.55 + 1
    jc @B
    retn

a rd 1 shl 20