Re: The hardest Euler problem

cac <cac@[EMAIL PROTECTED]
> writes Re: The hardest Euler problem
[..]
>> Someone posted this PARI/GP solution to problem 12:
 
>> n=0; until(numdiv(n*(n+1)/2) > 500, n++); n*(n+1)/2

>> He said it took about 50ms on his Intel 2.52GHz.

What else to expect with a built-in number-of-divisors function? 

> Sigh. My solution takes 1h45m. I think maybe PARI/GP knows things about
> factoring that I don't.

What you can easily see is that one only needs to count to below the 
square root of u1, because each successful division delivers you two 
valid divisors. If you take that into account, you solve the problem
in 800 ms (so short that I didn't think about making it faster).
The only (1-off ) complication is that u1 could be a perfect square 
(however, it follows from the formula it can't).

Assuming you are doing this in Forth (why else mention it here):

: #divisors ( u1 -- u2 )
	0 swap
	dup s>f fsqrt fround f>s 1+  ( prefect square?)
	1 ?do  dup i mod 0= 2 and rot + swap  loop  drop ;

> I didn't have much problem with 191. 192 on the other hand... I whipped
> out some code, looks good, runs quick, gets the wrong answer...

I also find that some of the higher-numbered problems can be surprisingly
simple. Unfortunately, some others can waste a day (44, 45 I can't solve
by brute force).

-marcel