# 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, 2011 at 23:17
• The 1min rule still applies? Feb 1, 2011 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, 2011 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, 2011 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, 2011 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, 2011 at 5:03

# x86 assembly (32-bit), 1 byte

Try it online!

A whole program that runs on Linux with 32-bit or 64-bit x86 CPU. It uses exactly 1 byte of stack memory (by dec esp) as the output buffer for a single character.

The other entries calling printf are actually using quite a lot of memory depending on the buffer size of the C output stream.

The code was a lot simpler, initially, as a direct port of @Anon.'s brute force approach. However, since that version took about 2 minutes to complete, I did a bit of optimizations to make it run within 25 seconds in TIO.

    movd xmm0, esp
mov esi, 1
mov edi, esi
jmp L0
.balign 16
L0:
inc esi
test edi, 1
jnz L0
tzcnt ecx, edi
mov ebx, edi
shr ebx, cl
inc ecx
mov ebp, 3
mov esp, 2
jmp L1e
.balign 16
L1:
mov eax, ebx
xor edx, edx
div ebp
cmp edx, 1
L1e:
mov eax, ebx
mov edx, 2863311531
mul edx
shr edx, 1
cmp edx, ebp
jae L1
imul esp, ecx
cmp esp, 500
jbe L0
mov esi, 1
mov eax, edi
mov ebp, 3435973837
jmp L2e
.balign 16
L2:
imul esi, esi, 10
L2e:
mul ebp
shr edx, 3
mov eax, edx
jnz L2
movd esp, xmm0
dec esp
jmp L3
.balign 16
L3:
mov eax, edi
xor edx, edx
div esi
mov edi, edx
mov [esp], al
mov eax, 4
mov ebx, 1
mov ecx, esp
mov edx, ebx
int 0x80
mov eax, esi
mul ebp
shr edx, 3
mov esi, edx
jnz L3
mov eax, 1
int 0x80