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




puts:	equ	9		; MS-DOS syscall to print a string
	cpu	8086
	org	100h
section	.text
	;;;	Generate first 1000 elements of Q sequence
	mov	dx,3		; DX = N
	mov	di,Q+4		; DI = place to store elements 
	mov	cx,998		; Generate 998 more terms
genq:	mov	si,dx		; SI = N
	sub	si,[di-2]	; SI -= Q[N-1]
	mov	bp,dx		; BP = N
	sub	bp,[di-4]	; BP -= Q[N-2]
	dec	si		; SI = 2*(SI-1) (0-indexed, 2 bytes/term)
	shl	si,1
	dec	bp		; Same for BP
	shl	bp,1
	mov	ax,[si+Q]	; Load Q[n-Q[n-1]]
	add	ax,[bp+Q]	; Add Q[n-Q[n-2]]
	stosw			; Store as Q[n]
	inc	dx		; Increment N 
	loop	genq
	;;;	Print first 10 elements
	mov	ah,puts
	mov	dx,m10
	int	21h
	mov	cx,10
	mov	bx,1
p10:	call	prterm
	inc	bx
	loop	p10 
	;;;	Print 1000th element
	mov	ah,puts
	mov	dx,m1000
	int	21h
	mov	bx,1000
	;;;	Print the term in BX
prterm:	push	bx		; Save term
	dec	bx
	shl	bx,1
	mov	ax,[bx+Q]	; Load term into AX
	mov	bp,10		; Divisor
	mov	bx,num		; Number buffer pointer
.dgt:	xor 	dx,dx
	div	bp		; Divide number by 10
	dec	bx
	add	dl,'0'		; DX = remainder, add '0'
	mov	[bx],dl		; Stored digit
	test	ax,ax		; Done yet?
	jnz	.dgt		; If not, find next digit
	mov	dx,bx		; Print the number
	mov	ah,puts
	int	21h
	pop 	bx		; Restore term
	ret
section	.data
m10:	db	'First 10 terms are: $'
m1000:	db	13,10,'1000th term is: $'
	db	'*****'		; Number placeholder
num:	db	' $'
Q:	dw	1,1
 