10
\$\begingroup\$

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

\$\endgroup\$
8
  • \$\begingroup\$ You should probably make the input variable or find another to exclude solutions which just hard-codes the result. \$\endgroup\$
    – sepp2k
    Jan 31, 2011 at 23:17
  • \$\begingroup\$ The 1min rule still applies? \$\endgroup\$
    – Eelvex
    Feb 1, 2011 at 11:53
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – sepp2k
    Feb 1, 2011 at 13:28
  • \$\begingroup\$ @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. \$\endgroup\$
    – sepp2k
    Feb 1, 2011 at 13:40
  • 1
    \$\begingroup\$ Use the "quoting" tool instead of the block code tool for quotes, it puts > before every line of the quote. \$\endgroup\$
    – Nick T
    Feb 3, 2011 at 15:08

3 Answers 3

14
\$\begingroup\$

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"
\$\endgroup\$
8
\$\begingroup\$

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.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ 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 \$\endgroup\$
    – gnibbler
    Feb 1, 2011 at 5:03
3
\$\begingroup\$

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
    add edi, 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
    adc esp, 0
    add ebp, 2
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
    add eax, '0'
    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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.