The definition of the sequence is colloquially described as:

   Starting with the list [1,1],
   Take the last number in the list so far: 1, I'll call it x.
   Count forward x places from the beginning of the list to find the first number to add (1)
   Count backward x places from the end of the list to find the second number to add (1)
   Add the two indexed numbers from the list and the result becomes the next number in the list (1+1)
   This would then produce [1,1,2] where 2 is the third element of the sequence.

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:

   a(1)=a(2)=1
   a(n)=a(a(n-1))+a(n-a(n-1))

The sequence begins:

   1, 1, 2, 2, 3, 4, 4, 4, 5, ...

Interesting features of the sequence are that:

   a(n)/n   tends to   0.5   as   n   grows towards infinity.
   a(n)/n   where   n   is a power of   2   is   0.5
   For   n>4   the maximal value of   a(n)/n   between successive powers of 2 decreases.



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

   │a(n)/n│ < 0.55  for all  n > p

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



Task

   Create a routine to generate members of the Hofstadter-Conway $10,000 sequence.
   Use it to show the maxima of   a(n)/n   between successive powers of two up to   2**20
   As a stretch goal:   compute the value of   n   that would have won the prize and confirm it is true for   n   up to 2**20


Also see

   Conways Challenge Sequence, Mallows' own account.
   Mathworld Article.


*        Hofstadter-Conway $10,000 sequence    07/05/2016
HOFSTADT START
         B      72(R15)            skip savearea
         DC     17F'0'             savearea
         STM    R14,R12,12(R13)    save registers
         ST     R13,4(R15)         link backward SA
         ST     R15,8(R13)         link forward SA
         LR     R13,R15            establish addressability
         USING  HOFSTADT,R13       set base register
         LA     R4,2               pow2=2
         LA     R8,4               p2=2**pow2
         MVC    A+0,=F'1'          a(1)=1
         MVC    A+4,=F'1'          a(2)=1
         LA     R6,3               n=3
LOOPN    C      R6,UPRDIM          do n=3 to uprdim
         BH     ELOOPN
         LR     R1,R6              n
         SLA    R1,2
         L      R5,A-8(R1)         a(n-1)
         LR     R1,R5
         SLA    R1,2
         L      R2,A-4(R1)         a(a(n-1))
         LR     R1,R6              n
         SR     R1,R5              n-a(n-1)
         SLA    R1,2
         L      R3,A-4(R1)         a(n-a(n-1)
         AR     R2,R3              a(a(n-1))+a(n-a(n-1))
         LR     R1,R6              n
         SLA    R1,2
         ST     R2,A-4(R1)         a(n)=a(a(n-1))+a(n-a(n-1))
         LR     R1,R6              n
         SLA    R1,2
         L      R2,A-4(R1)         a(n)
         MH     R2,=H'10000'       fixed point 4dec
         SRDA   R2,32
         DR     R2,R6              /n
         LR     R7,R3              r=a(n)/n
         C      R7,=F'5500'        if r>=0.55
         BL     EIF1
         LR     R9,R6              mallows=n
EIF1     C      R7,PEAK            if r>peak
         BNH    EIF2
         ST     R7,PEAK            peak=r
         ST     R6,PEAKPOS         peakpos=n
EIF2     CR     R6,R8              if n=p2
         BNE    EIF3
         LR     R1,R4              pow2
         BCTR   R1,0               pow2-1
         XDECO  R1,XDEC            edit pow2-1
         MVC    PG1+18(2),XDEC+10
         XDECO  R4,XDEC            edit pow2
         MVC    PG1+27(2),XDEC+10
         L      R1,PEAK            peak
         XDECO  R1,XDEC            edit peak
         MVC    PG1+35(4),XDEC+8
         L      R1,PEAKPOS         peakpos
         XDECO  R1,XDEC            edit peakpos
         MVC    PG1+45(5),XDEC+7
         XPRNT  PG1,80             print buffer
         LA     R4,1(R4)           pow2=pow2+1
         SLA    R8,1               p2=2**pow2
         MVC    PEAK,=F'5000'      peak=0.5
EIF3     LA     R6,1(R6)           n=n+1
         B      LOOPN
ELOOPN   L      R1,L               l
         XDECO  R1,XDEC            edit l
         MVC    PG2+6(2),XDEC+10
         XDECO  R9,XDEC            edit mallows
         MVC    PG2+29(5),XDEC+7
         XPRNT  PG2,80             print buffer
RETURN   L      R13,4(0,R13)       restore savearea pointer
         LM     R14,R12,12(R13)    restore registers
         XR     R15,R15            return code = 0
         BR     R14                return to caller
         LTORG  
L        DC     F'12'
UPRDIM   DC     F'4096'            2^L
PEAK     DC     F'5000'            0.5 fixed point 4dec
PEAKPOS  DC     F'0'
XDEC     DS     CL12
PG1      DC CL80'maximum between 2^xx and 2^xx is 0.xxxx at n=xxxxx'
PG2      DC CL80'for l=xx : mallows number is xxxxx'
A        DS     4096F              array a(uprdim)
         REGEQU
         END    HOFSTADT