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

cbrulak

Posted 2011-01-31T23:11:36.587

Reputation: 265

I was hoping for a regular shortest code golf and if it would have been I would have posted require'prime';i=500;n=s*(s+1)/2;i=s+1;while(n.prime_division.transpose[1].map{|n|n+1}.reduce(&:*)<s);n+=i; i+=1;end;n #Ruby Euler #12 but since it isn't I can't do that. – Jonas Elfström – 2012-03-29T14:23:28.740

You should probably make the input variable or find another to exclude solutions which just hard-codes the result. – sepp2k – 2011-01-31T23:17:53.647

The 1min rule still applies? – Eelvex – 2011-02-01T11:53:35.443

1@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. – sepp2k – 2011-02-01T13:28:29.007

@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. – sepp2k – 2011-02-01T13:40:09.040

1Use the "quoting" tool instead of the block code tool for quotes, it puts > before every line of the quote. – Nick T – 2011-02-03T15:08:00.310

How are you counting memory? Number of registers used? – Peter Taylor – 2011-02-04T11:48:30.940

No time limit? Here is a solution that uses 0 bytes: while 1:pass. When it finishes it prints the answer on the screen. – Alexandru – 2011-02-04T15:59:08.723

Answers

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"

Hoa Long Tam

Posted 2011-01-31T23:11:36.587

Reputation: 1 902

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.

Anon.

Posted 2011-01-31T23:11:36.587

Reputation: 1 799

1you 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 – gnibbler – 2011-02-01T05:03:50.937