# Project Euler Problem 12: optimize memory usage

I am referring to Project Euler #12. Write the solution in any language you want, but consume the least amount of memory while executing. Running time is not measure in this case.

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?

No hardcoding of values/results. Honour system here folks :)

• You should probably make the input variable or find another to exclude solutions which just hard-codes the result. Jan 31 '11 at 23:17
• The 1min rule still applies? Feb 1 '11 at 11:53
• @Joey: Project Euler doesn't need to since it isn't a code competition. We do. Yes, there's nothing on Project Euler preventing me from first creating a program which calculates the result and then creating another program with the result hard coding. But since I only send in the solution, not the code, I have no reason to do that. Here OTOH the first person to hardcode the result would be trivially the winner, rendering the competition pointless. Thus such solutions should be made impossible. Feb 1 '11 at 13:28
• @Joey: It's also common sense that it's wrong to murder people. That doesn't mean that there's no need to put that notion into law. The edit was made in response to my comment if it had been there before, I wouldn't have posted my comment. Feb 1 '11 at 13:40
• Use the "quoting" tool instead of the block code tool for quotes, it puts > before every line of the quote. Feb 3 '11 at 15:08

MIPS32 Assembly. Uses 8 bytes of memory (4 for format string, 4 for saving a pointer), everything else stays in registers. This should work in x86-64, too, but ia32 will probably require some temporary values to be stored in memory.

    .text
.globl main
main:
xor $t0,$t0, $t0 xor$t1, $t1,$t1
loop1:
addiu $t0,$t0, 1
addu $t1,$t1, $t0 addiu$t3, $zero, 1 addiu$t5, $zero, 2 srl$t6, $t1, 1 loop2: slt$t4, $t6,$t5
bne $t4,$zero, loop2end
div $t1,$t5
mfhi $t4 bne$t4, $zero, non_divisor addiu$t3, $t3, 1 non_divisor: addiu$t5, $t5, 1 j loop2 loop2end: slti$t4, $t3, 501 bne$t4, $zero, loop1 la$a0, str
addu $a1,$t1, $zero addiu$sp, $sp, -4 sw$ra, 0($sp) jal _printf lw$ra, 0($sp) addiu$sp, $sp, 4 jr$ra
.data
str:
.asciiz "%d\n"


With no running time measure, but counting memory usage, the "naive" method of finding divisors is the way to go.

int i = 1;
int n = 1;
while(true)
{
n += ++i; //get next triangle number
int nd = 1;
for(int d = 1; d <= n/2; d++)
if(n % d == 0)
nd++;
if(nd > 500) break;
}
printf("Result: %d", n);


Uses four locals + any compiler temporaries, no recursion or heap memory.

• you can compute n everywhere it is needed using n=(i+1)*i/2. Substituting in the two places where n is used will save the extra variable Feb 1 '11 at 5:03