For this task, the Stern-Brocot sequence is to be generated by an algorithm similar to that employed in generating the Fibonacci sequence.

 The first and second members of the sequence are both 1:
     1, 1
 Start by considering the second member of the sequence
 Sum the considered member of the sequence and its precedent, (1 + 1) = 2, and append it to the end of the sequence:
     1, 1, 2
 Append the considered member of the sequence to the end of the sequence:
     1, 1, 2, 1
 Consider the next member of the series, (the third member i.e. 2)
 GOTO 3
 
         ─── Expanding another loop we get: ───

 Sum the considered member of the sequence and its precedent, (2 + 1) = 3, and append it to the end of the sequence:
     1, 1, 2, 1, 3
 Append the considered member of the sequence to the end of the sequence:
     1, 1, 2, 1, 3, 2
 Consider the next member of the series, (the fourth member i.e. 1)


The task is to

 Create a function/method/subroutine/procedure/... to generate the Stern-Brocot sequence of integers using the method outlined above.
 Show the first fifteen members of the sequence. (This should be: 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4)
 Show the (1-based) index of where the numbers 1-to-10 first appears in the sequence.
 Show the (1-based) index of where the number 100 first appears in the sequence.
 Check that the greatest common divisor of all the two consecutive members of the series up to the 1000th member, is always one.

Show your output on this page.



Related tasks

   Fusc sequence.
   Continued fraction/Arithmetic


Ref

 Infinite Fractions - Numberphile (Video).
 Trees, Teeth, and Time: The mathematics of clock making. 
 A002487 The On-Line Encyclopedia of Integer Sequences.


puts:	equ	9
	cpu	8086
	bits	16
	org	100h
section	.text
	;;;	Generate the first 1200 elemets of the Stern-Brocot sequence
	mov	cx,600	; 2 elements generated per loop
	mov	si,seq
	mov	di,seq+2
	lodsb
	mov	ah,al	; AH = predecessor
genseq:	lodsb		; AL = considered member
	add	ah,al	; AH = sum
	xchg	ah,al	; Swap them (AL = sum, AH = member)
	stosw		; Write sum and current considered member
	loop	genseq	; Loop 600 times
	;;;	Print first 15 members of sequence
	mov	si,seq
	mov	cx,15
p15:	lodsb		; Get member
	cbw
	call	prax 	; Print member
	loop	p15
	call	prnl 
	;;;	Print first occurrences of [1..10]
	mov	al,1
	mov	cx,10
	call	find
	call	prnl 
	;;;	Print first occurrence of 100
	mov	al,100
	mov	cx,1
	call	find
	call	prnl
	;;;	Check pairs of GCDs
	mov	cx,1000	; 1000 times
	mov	si,seq
	lodsb
gcdchk:	mov	ah,al	; AH = last member, AL = current member
	lodsb
	mov	dx,ax	; Calculate GCD
	call	gcd
	dec	dl	; See if it is 1
	jnz	.fail	; If not, failure
	loop	gcdchk	; Otherwise, check next pair
	mov	dx,gcdy	; GCD of all pairs is 0
	jmp	pstr
.fail:	mov	dx,gcdn	; GCD of current pair is not 0
	call	pstr
	mov	ax,si
	sub	ax,seq+1
	jmp	prax
	;;;	DL = gcd(DL,DH)
gcd:	cmp	dl,dh
	jl	.lt	; DL < DH
	jg	.gt	; DL > DH
	ret
.lt:	sub	dh,dl	; DL < DH
	jmp	gcd
.gt: 	sub	dl,dh	; DL > DH
	jmp	gcd
	;;;	Print indices of CX consecutive numbers starting
	;;;	at AL.
find:	mov	di,seq
	push	cx	; Keep loop counter
	mov	cx,-1
	repne	scasb	; Find AL starting at [DI]
	pop	cx	; Restore loop counter
	xchg	si,ax	; Keep AL in SI
	mov	ax,di	; Calculate index in sequence
	sub	ax,seq
	call	prax	; Output
	xchg	si,ax	; Restore AL 
	inc	ax	; Increment
	loop 	find	; Keep going CX times
	ret 
	;;;	Print newline
prnl:	mov	dx,nl
	jmp	pstr
	;;;	Print number in AX
	;;;	Destroys AX, BX, DX, BP
prax:	mov	bp,10	; Divisor
	mov	bx,numbuf
.loop:	xor	dx,dx	; DX = 0
	div	bp	; Divide DX:AX by 10; DX = remainder
	dec	bx	; Move string pointer back
	add	dl,'0'	; Make ASCII digit
	mov	[bx],dl	; Write digit
	test	ax,ax	; Any digits left?
	jnz	.loop
	mov	dx,bx
pstr:	mov	ah,puts	; Print number string
	int	21h
	ret 
section	.data
gcdn:	db	'GCD not 1 at: $'
gcdy:	db	'GCD of all pairs of consecutive members is 1.$'
	db	'*****'
numbuf:	db	' $'
nl:	db	13,10,'$'
seq:	db	1,1