Subject: Sums of digits and other tricks and factor()
From: Richard Hennessy
Date: Thu, 10 Dec 2009 17:29:47 -0500
Hi List,
I have been wondering why factor() is slow on factoring big exact numbers that are in the form y/x where x is a big even
integer and y is an integer. It is easy to tell that factor 8788797887776565343256785434546789796543568097876592 is
factorable by 2 just by looking at the last digit.
I have a function of two variables defined as a power series f(x,y,terms) and another home made function factorsum().
factorsum(f(x,y,48),y)$ /* this is my factorsum() function not Maxima's.*/
Evaluation took 2.5900 seconds (2.5900 elapsed)
but
factorsum(f(1/2,y,48), y)$
Evaluation took 58.5300 seconds (58.5300 elapsed)
takes a lot longer. I have determined that the result is slower because of the call to factor() inside factorsum() and
the time it takes to factor y^n/(2^48 * . . .) + . . . . There are a lot of tricks I know for decimal numbers that can
tell quickly that a number is factorable by 2,3 5,7,11. I imagine there are similar tricks that can be used in binary
and for larger primes.
Rich