## Friday, 7 March 2014

### Triangle numbers

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

```.syntax unified

.align 2

.section .rodata
resstring:
.asciz "%d\n"

.equ    last, 250       @ we count up to the square root - so half of the divisors will
@ be necessarily less than the square root and half above.

icount .req r4          @ it is possible to write FORTRAN in any language :-)
jcount .req r5
tmp    .req r6
num    .req r7

.text
.align  2
.global get_num_divisors
.type   get_num_divisors, %function

@ we use jcount to hold current divisor and icount to hold the number of divisors seen
@ num is passed as r0 and the number of divisors is returned.
get_num_divisors:
stmfd   sp!, {r4-r7, lr}
mov     num, r0
mov     icount, 0
mov     jcount, 1
jstart:
mov     r0, num
mov     r1, jcount
bl      divide
teq     r1, 0
beq     factor
b       nextj
factor:
add     icount, icount, 1
nextj:
add     jcount, jcount, 1
mul     tmp, jcount, jcount
cmp     num, tmp
bgt     jstart
mov     r0, icount
ldmfd   sp!, {r4-r7, pc}

.align  2
.global main
.type   main, %function

main:
stmfd   sp!, {r4-r7, lr}
mov     num, 0
mov     icount, 0
mov     jcount, 1
loop:
cmp     num, #last
bge     printme
add     icount, icount, jcount
mov     r0, icount
bl      get_num_divisors
mov     num, r0

add     jcount, jcount, 1
b       loop

printme:
mov     r1, icount
ldr     r0, =resstring  @ store address of start of string to r0
bl      printf

mov     r0, 0
ldmfd   sp!, {r4-r7, pc}
mov     r7, 1   @ set r7 to 1 - the syscall for exit
swi     0               @ then invoke the syscall from linux
```
```divide.s
.syntax unified
# divide takes value in r0, divisor in r1 and returns dividend in r0 and modulus in r1
.global divide
.type divide, %function

divide:
stmfd   sp!, {lr}
# see http://infocenter.arm.com/help/topic/com.arm.doc.ihi0043d/IHI0043D_rtabi.pdf
bl  __aeabi_uidivmod
ldmfd   sp!, {pc}
```