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
X! Y! Z!
a! b! c!
WLOG let's assume that X > Y > Z and a > b > c. Also let's assume that
+ b > Y , X > a (weaker assumption: Z > c)...<p>
NOTE: if we divide X!/a! we will have (X-a) elements <p>
To Prove: (X-a) + (Z-c) + (b-Y) is the shortest list one can find
or in other words
(X-a) + (Z-c) + (b-Y) <= (X-p) + (Z-q) + (r-Y) for any p,q,r in permut
From the above equation since b > Y and Z > c, r should be equal to ei
+ther a or b. If r = b then the solution is trivial<p>
If r = a then we get
(X-a) + (Z-c) + (b-Y) ?<= (X-b) + (Z-c) + (a-Y)
-a - c + b ?<= -b -c + a
-a + b ?<= -b + a ====> YES
since a > b we see that r = a is not the smallest list so r = b<p>
Similarly we can also show that (X-a) + (Z-c) + (b-Y) <= (X-a) + (Y-c)
+ + (b-Z)
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..
Are you posting in the right place? Check out Where do I post X? to know for sure.
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
Want more info? How to link
or How to display code and escape characters
are good places to start.