Hofstadter Q sequence


 







Q
(
1
)



=
Q
(
2
)
=
1
,




Q
(
n
)



=
Q


(


n
−
Q
(
n
−
1
)


)


+
Q


(


n
−
Q
(
n
−
2
)


)


,

n
>
2.






{\displaystyle {\begin{aligned}Q(1)&=Q(2)=1,\\Q(n)&=Q{\big (}n-Q(n-1){\big )}+Q{\big (}n-Q(n-2){\big )},\quad n>2.\end{aligned}}}




It is defined like the Fibonacci sequence, but whereas the next term in the Fibonacci sequence is the sum of the previous two terms, in the Q sequence the previous two terms tell you how far to go back in the Q sequence to find the two numbers to sum to make the next term of the sequence.



Task

 Confirm and display that the first ten terms of the sequence are: 1, 1, 2, 3, 3, 4, 5, 5, 6, and 6 
 Confirm and display that the 1000th term is:   502


Optional extra credit
 Count and display how many times a member of the sequence is less than its preceding term for terms up to and including the 100,000th term.
 Ensure that the extra credit solution   safely   handles being initially asked for an nth term where   n   is large.

(This point is to ensure that caching and/or recursion limits, if it is a concern, is correctly handled).




*        Hofstrader q sequence for any n -   18/10/2015
HOFSTRAD CSECT
         USING  HOFSTRAD,R15       set base register
         MVC    Q,=F'1'            q(1)=1
         MVC    Q+4,=F'1'          q(2)=1
         LA     R4,1               i=1
LOOPI    C      R4,N               do i=1 to n
         BH     ELOOPI
         C      R4,=F'3'           if i>=3 then
         BL     NOTREC
         LR     R1,R4              i
         SLA    R1,2               i*4
         L      R2,Q-8(R1)         q(i-1)
         LR     R1,R4              i
         SR     R1,R2              i-q(i-1)
         SLA    R1,2               *4
         L      R2,Q-4(R1)         r2=q(i-q(i-1))
         LR     R1,R4              i
         SLA    R1,2               i*4
         L      R3,Q-12(R1)        q(i-2)
         LR     R1,R4              i
         SR     R1,R3              i-q(i-2)
         SLA    R1,2               *4
         L      R3,Q-4(R1)         r3=q(i-q(i-2))
         AR     R2,R3              r2=r2+r3
         LR     R1,R4              i
         SLA    R1,2               i*4
         ST     R2,Q-4(R1)         q(i)=q(i-q(i-1))+q(i-q(i-2))
NOTREC   C      R4,=F'10'          if i<=10
         BNH    PRT
         C      R4,N               or i=n then
         BNE    NOPRT
PRT      XDECO  R4,XD              edit i
         MVC    PG+2(4),XD+8       output i
         LR     R1,R4              i
         SLA    R1,2               i*4
         L      R2,Q-4(R1)         q(i)
         XDECO  R2,XD              edit q(i)
         MVC    PG+10(4),XD+8      output q(i)
         XPRNT  PG,80              print buffer
NOPRT    LA     R4,1(R4)           i=i+1
         B      LOOPI
ELOOPI   XR     R15,R15            set return code
         BR     R14                return to caller
PG       DC     CL80'n=...., q=....'  buffer
XD       DS     CL12               temporary variable
         LTORG                     insert literals for addressability
N        DC     F'1000'            n=1000
Q        DS     1000F              array q(1000) 
         YREGS
         END    HOFSTRAD