?

Log in

No account? Create an account

Thu, Nov. 4th, 2010, 11:29 am
One more FRACTRAN post

Here's a program to calculate factorials:
(2^n -> 3^(n!), provided that n>0):
115/38 19/23 17/19 4147/51 17/29 31/17 259/155 41/31 129/481 37/43 17/37 47/533 41/47 53/41 177/583 53/59 61/53 67/427 1/61 355/469 67/71 17/67 57/2
Of course, the numbers involved here are very large.  It took my emulator (written in Racket - formerly PLT Scheme) about 75 seconds (and 82342 iterations) to calculate that 7!=5040.  The numbers involved are very large.  The final state is, of course, 3^5040.  However, the largest state at any time was 11^5040 * 13^5040 * 41 - a number with 10865 digits.

I'd like to write a program to calculate Catalan Numbers.  Unfortunately, recursion (using the formula C(0) = 1 and C(n+1) = Sum (i = 0, n, C(i)C(n-i))) is probably right out since all variables are global.  That leaves formula C(n) = choose(2n, n) - choose(2n, n+1), but since both of those terms require multiplying large numbers, the execution time will be astronomical just to check the smallest cases.