7
\$\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 '11 at 23:17
  • \$\begingroup\$ The 1min rule still applies? \$\endgroup\$
    – Eelvex
    Feb 1 '11 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 '11 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 '11 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 '11 at 15:08
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 '11 at 5:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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