|Perl: the Markov chain saw|
Re^3: Algorithm for cancelling common factors between two lists of multiplicandsby sk (Curate)
|on Aug 12, 2005 at 05:20 UTC||Need Help??|
I am not sure if you had a chance to look at my node Re^7: Algorithm for cancelling common factors between two lists of multiplicands
I guess my approach is same as Limbic~Region as I was using subtraction of lower factorial terms with higher ones.
I copied the input list from one of your previous examples and I have 45700 instead of 4570 but aside from that the implementation should be easy to understand.
I guess if you sort numerator and denominator and subtract them you should be all set. I have not proved this formally but here is a stab at a simple proof that shows sorting and subtracting should work...
Let the fraction be
I don't think this is a rigourous proof this method but i sort of feel sorting and subtracting should give us what we need...
PS: I think there will be 47448 elements and not 47444 as you suggested? as you need to count the first element too..