the algo train

I can only assume that shoen's commute involves taking amtrack from LA to SF which would give him adequate time to verify the 5604 partitions of 30 by staring at them.

Sure, you can do better than Euclid for gcd. There is Webber's accelerated GCD which is used by gmp and Mathematica. Here's the paper for the next few hours or so.

Trying to factor a bunch of number to do LCM quickly would probably lead to either a) a very slow LCM or b) the breaking of RSA. It appears UMB scheme does not do a) since it's fast and b) seems unlikely. Being bored (YouCanNeverLookAtTooManyShemeImplementations), I took a look and it seems to do what one would expect.

Private void Varying_Number_LCM()
{
   Integer arg_count = Get_Apply_Numargs(
                                   Expression_Register );
    
	if ( arg_count >= 2 )
	{
		Value_Register = Top(arg_count);
		Iterate_Over_Operands( arg_count, 
                                      Num_Ops.Number_LCM );
	}
     [etc]

 [and also]

 Public void Bignum_LCM()
{
	/* LCM(a,b) = (a*b)/GCD(a,b)  */
	[etc]

lcm is in terms of gcd and multi-arg lcm is lcm chained. (the above code from UMB Scheme is GPL'ed so we must be still on topic...)

As to partitions, I'm not sure anything can really count for 'efficient' since their number grows exponentially. One shouldn't need memoization, the easiest way to generate them is to just spew them out in reverse lexicographical order. This can be done in constant amortized time, see the Combinatorial Object Server for an example. A Pascal or C program can be grabbed from the bottom of this www.theory.csc.uvic.ca/~cos/inf/nump/NumPartition.html page which the form won't let me enter as an href because it's too wide.

If you just want the number p(n), for large n, there is the Ramanujan/Hardy thingie...

p(n) approx= (e^(k sqrt(n))) / (4n sqrt(3)) where k = pi sqrt(2/3)

They also came up with an inf. series which can be used to get the desired accuracy. Should be extractable from number theory references.